Scala中的流序列

Question

假设存在序列a[i] = f(a[i-1], a[i-2], ... a[i-k])。如何在Scala中使用streams进行编码?

Answer 1

可以将其推广到任何k，使用a和另一个k参数的数组，并且具有，f.i，具有rest...参数的函数。

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)

为了有第1000次做next.drop(1000)

一个更新，展示了如何使用可变变量完成此操作。注意，对于传递的函数没有校验:

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)

}

Answer 2

这样可以吗?(a[i] = f(a[i-k]， a[i-k+1]，…)A [i-1])而不是A [i] = f(A [i-1]， A [i-2]，…a[I -k])，因为我更喜欢这样做)

/**
  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 }
}

例如，下面的代码生成斐波那契数列。

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)

下面的代码可以生成一个序列{an}，其中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)

Answer 3

简短的答案，你可能正在寻找，是一个模式来定义你的Stream，一旦你已经为f的密度(即你有一个固定类型的f)固定了一个选择的k。下面的模式给你一个Stream, n -th元素是你的序列的术语a[n]:

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

(credit:它非常接近andy petrella的答案，除了初始元素是正确设置的，因此流中的秩与序列中的秩匹配)

如果你想在k上泛化，这是可能的在Scala中以一种类型安全的方式(带性检查)，使用优先级重叠的隐式。代码(约80行)可在这里作为要点。恐怕我有点忘乎所以了，把它解释成一个详细的"& & &;

Answer 4

不幸的是，我们不能在泛化number的同时又保证类型安全。所以我们必须手动完成:

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)
    }
  }
}

得到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))(_ + _ + _)

…，最多22.

我希望这个模式在某种程度上变得清晰了。(当然，我们可以用单独的参数改进和交换initials元组。这为以后使用它时节省了一对括号。)如果将来有一天，Scala宏语言出现了，希望这将更容易定义。