Scalaでストリームを持つシーケンス

Question

シーケンスa[i] = f(a[i-1], a[i-2], ... a[i-k])があるとします。 Scalaでstreamsを使用してどのようにコード化しますか？

Answer 1

aの配列ともう1つのkの配列を使用し、f.i.のパラメータがrest...の配列を使用して任意のkに対して一般化することができます。第千を持っているために、

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) 

が、これは可変引数で行うことができる方法を示すために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

までの私は、パターンが明確で何とかなっている願っています。 （もちろん、別の引数を使ってinitialsタプルを改良して交換することもできます。これにより、後で使用する際に一対のカッコが節約されます）。将来、スカラマクロ言語が到着すると、これはうまく定義しやすくなります。

Answer 3

これは問題ありませんか？ [i] = f（a [i-1]、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）配列は（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

短い答えは、あなたはおそらく探していることを、あなたは（つまり、あなたは、固定型を持つfのアリティのため選ばれたkを固定した後、あなたのStreamを定義するためのパターンであり、次のパターンは、Streamです。n番目の要素は、シーケンスの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)) 

（クレジット：それは最初の要素が正しく設定されていることを除いて、アンディpetrellaのanswerに非常に近く、その結果、ストリーム内のランクが連続していることと一致する）

あなたの場合kで一般化したい場合は、Scalaでタイプセーフな方法（アリティチェック付き）でを使用することができます。優先順位付けされたオーバーラッピングimplicitsを使用します。コード（~80行）は要点hereとして利用可能です。私はちょっと気を取られてしまい、詳細& overlong blog投稿thereと説明しました。