具有斯卡拉流的序列

Question

假設有一個序列a[i] = f(a[i-1], a[i-2], ... a[i-k])。你將如何在Scala中使用streams進行編碼？

Answer 1

將有可能將它推廣到任何k，使用a和另一個k參數的數組，並且具有帶參數rest...的函數f.i.。

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

不幸的是，我們不能一概而論在數量和類型可以在同一時間的安全。因此，我們必須手工做這一切：

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

我希望圖案清晰某種方式得到。 （我們當然可以改進和交換具有不同參數的元組，這爲我們在後面使用它時節省了一對括號。）如果將來有一天，Scala宏語言到達，這有希望更容易定義。

Answer 3

可以嗎？ （a [i] = f（a [i-1]，a [i-1]）而不是a [i-1] [I-2]，...一個[IK]），由於我寧願這樣）

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

下面的代碼可以產生一個序列{一個}其中，a1 = 1，A2 = 2，A 3 = 3，第（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 4

簡短的回答，您可能尋找，是定義你的Stream模式，一旦你已經固定的f的元數選定k（即你有一個固定的類型對於f）。以下模式爲您提供了一個Stream其中n第012個元素是您的序列中的術語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)) 

（來源：它是非常靠近安迪彼得雷拉的answer，除了最初的元素設置正確，因此在流等級匹配的序列）

如果您想要推廣到k，這是可能的在類型安全的方式（與arity檢查）斯卡拉，使用優先級重疊implicits。該代碼（約80行）可作爲要求here。恐怕我有一點點遺忘，並將其解釋爲詳細的&超長博客文章there。