5

Suppose there is a sequence a[i] = f(a[i-1], a[i-2], ... a[i-k]). How would you code it using streams in Scala?

2
  • 2
    I'm trying to understand the rules of the sequence. What is k? What is a[0] (the first element in the stream)? What is a[1]? Dec 27, 2011 at 11:33
  • @toddsundsted Suppose I know the first k elements of the sequence: a[0], a[1], ..., a[1]. Now I want to calculate a[n] for n > k using function f.
    – Michael
    Dec 27, 2011 at 11:53

4 Answers 4

3

It will be possible to generalize it for any k, using an array for a and another k parameter, and having, f.i., the function with a rest... parameter.

def next(a1:Any, ..., ak:Any, f: (Any, ..., Any) => Any):Stream[Any] {
  val n = f(a1, ..., ak)
  Stream.cons(n, next(a2, ..., n, f))
}

val myStream = next(init1, ..., initk)

in order to have the 1000th do next.drop(1000)

An Update to show how this could be done with varargs. Beware that there is no arity check for the passed function:

object Test extends App {

def next(a:Seq[Long], f: (Long*) => Long): Stream[Long] = {
  val v = f(a: _*)
  Stream.cons(v, next(a.tail ++ Array(v), f))
}

def init(firsts:Seq[Long], rest:Seq[Long], f: (Long*) => Long):Stream[Long] = {
  rest match {
    case Nil => next(firsts, f)
    case x :: xs => Stream.cons(x,init(firsts, xs, f))
  }
}

def sum(a:Long*):Long = {
  a.sum
}

val myStream = init(Seq[Long](1,1,1), Seq[Long](1,1,1), sum)


myStream.take(12).foreach(println)

}

5
  • How do you get the initial kelements ?
    – Francois G
    Dec 27, 2011 at 12:15
  • It's not part of the question, I've assumed that they are known. As it is for Fibonacci, you set the first two as being 0 and 1. Dec 27, 2011 at 12:30
  • @andypetrella yes, you are right, I assume the first k elements are known.
    – Michael
    Dec 27, 2011 at 12:36
  • 1
    I meant how does your function answer the question of returning a[i], for 1 ≤ i ≤ k. We all agreee that those k initial elements are assumed to be known, but I wanted to point out that from what I understand, your myStream starts at a[k+1] and that dropping the first 1000 won't give you a[1000].
    – Francois G
    Dec 27, 2011 at 12:38
  • Okay, I didn't took that. You're right for the first. What could be done is to Stream the first k a, then delegate to the next function. I'm gonna update it with the related solution including varargs... but no check on arity :/ Dec 27, 2011 at 13:14
3

Is this OK? (a[i] = f(a[i-k], a[i-k+1], ... a[i-1]) instead of a[i] = f(a[i-1], a[i-2], ... a[i-k]), since I prefer to this way)

/**
  Generating a Stream[T] by the given first k items and a function map k items to the next one.
*/
def getStream[T](f : T => Any,a : T*): Stream[T] = { 
  def invoke[T](fun: T => Any, es: T*): T = {
    if(es.size == 1) fun.asInstanceOf[T=>T].apply(es.head)
    else invoke(fun(es.head).asInstanceOf[T => Any],es.tail :_*)
  }
  Stream.iterate(a){ es => es.tail :+ invoke(f,es: _*)}.map{ _.head }
}

For example, the following code to generate Fibonacci sequence.

scala> val fn = (x: Int, y: Int) => x+y
fn: (Int, Int) => Int = <function2>

scala> val fib = getStream(fn.curried,1,1)
fib: Stream[Int] = Stream(1, ?)

scala> fib.take(10).toList
res0: List[Int] = List(1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

The following code can generate a sequence {an} where a1 = 1, a2 = 2, a3 = 3, a(n+3) = a(n) + 2a(n+1) + 3a(n+2).

scala> val gn = (x: Int, y: Int, z: Int) => x + 2*y + 3*z
gn: (Int, Int, Int) => Int = <function3>

scala> val seq = getStream(gn.curried,1,2,3)
seq: Stream[Int] = Stream(1, ?)

scala> seq.take(10).toList
res1: List[Int] = List(1, 2, 3, 14, 50, 181, 657, 2383, 8644, 31355)
3

The short answer, that you are probably looking for, is a pattern to define your Stream once you have fixed a chosen k for the arity of f (i.e. you have a fixed type for f). The following pattern gives you a Stream which n-th element is the term a[n] of your sequence:

def recStreamK [A](f : A ⇒ A ⇒ ... A) (x1:A) ... (xk:A):Stream[A] =
  x1 #:: recStreamK (f) (x2)(x3) ... (xk) (f(x1)(x2) ... (xk))

(credit : it is very close to the answer of andy petrella, except that the initial elements are set up correctly, and consequently the rank in the Stream matches that in the sequence)

If you want to generalize over k, this is possible in a type-safe manner (with arity checking) in Scala, using prioritized overlapping implicits. The code (˜80 lines) is available as a gist here. I'm afraid I got a little carried away, and explained it as an detailed & overlong blog post there.

2

Unfortunately, we cannot generalize over number and be type safe at the same time. So we’ll have to do it all manually:

def seq2[T, U](initials: Tuple2[T, T]) = new {
  def apply(fun: Function2[T, T, T]): Stream[T] = {
    initials._1 #::
    initials._2 #::
    (apply(fun) zip apply(fun).tail).map {
      case (a, b) => fun(a, b)
    }
  }
}

And we get def fibonacci = seq2((1, 1))(_ + _).

def seq3[T, U](initials: Tuple3[T, T, T]) = new {
  def apply(fun: Function3[T, T, T, T]): Stream[T] = {
    initials._1 #::
    initials._2 #::
    initials._3 #::
    (apply(fun) zip apply(fun).tail zip apply(fun).tail.tail).map {
      case ((a, b), c) => fun(a, b, c)
    }
  }
}

def tribonacci = seq3((1, 1, 1))(_ + _ + _)

… and up to 22.

I hope the pattern is getting clear somehow. (We could of course improve and exchange the initials tuple with separate arguments. This saves us a pair of parentheses later when we use it.) If some day in the future, the Scala macro language arrives, this hopefully will be easier to define.

1
  • Hmm, the defs should be lazy vals rather.
    – Debilski
    Dec 27, 2011 at 13:51

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.