CODEWITHSUNDEEP
scalastream
Michael
Michael

Reputation: 10303

Sequence with Streams in Scala

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?

Upvotes: 5

Views: 2090

Answers (4)

Francois G
Francois G

Reputation: 11985

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.

Upvotes: 3

Eastsun
Eastsun

Reputation: 18859

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)

Upvotes: 3

Andy Petrella
Andy Petrella

Reputation: 4345

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)

}

Upvotes: 3

Debilski
Debilski

Reputation: 67838

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.

Upvotes: 2

Related Questions