Sequenza con flussi in Scala

Question

Supponiamo che esista una sequenza a[i] = f(a[i-1], a[i-2], ... a[i-k]). Come lo codificheresti usando streams in Scala?

Answer 1

Sarà possibile generalizzarlo per ogni k, utilizzando una matrice per a e un altro parametro k e avendo, f.i., la funzione con un parametro 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) 

al fine di avere il 1000 fanno next.drop(1000)

Un aggiornamento per mostrare come questo potrebbe essere fatto con varargs. Fate attenzione che non v'è alcun controllo arity per la funzione passata:

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

Purtroppo, non possiamo generalizzare su numero e al sicuro al tempo stesso tipo. Quindi dovremo fare tutto manualmente:

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

E arriviamo 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))(_ + _ + _) 

... e fino a 22.

Spero che il modello è sempre chiaro in qualche modo. (Potremmo, naturalmente, migliorare e scambiare la tupla initials con argomenti separati.Questo ci risparmia un paio di parentesi più tardi quando lo usiamo.) Se un giorno, in futuro, arriverà il linguaggio macro di Scala, si spera che sarà più facile da definire.

Answer 3

È OK? (a [i] = f (a [ik], a [i-k + 1], ... a [i-1]) anziché a [i] = f (a [i-1], a [i-2], ... una [ik]), dal momento che preferisco in questo modo)

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

ad esempio, il seguente codice per generare la sequenza di Fibonacci.

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) 

Il codice seguente può generare una sequenza {un} dove 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 4

la risposta breve, che si sta probabilmente cercando, è un modello per definire la Stream una volta che avete fissato un prescelto k per l'arietà di f (cioè si dispone di un tipo fisso per f). Il seguente modello ti dà un che n -esimo elemento è il termine a[n] della sequenza:

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

(di credito: è molto vicino al answer di andy Petrella, tranne che gli elementi iniziali sono impostati correttamente, e di conseguenza il rango nel flusso partite che nella sequenza)

Se voglio generalizzare su k, questo è possibile in modo sicuro per il tipo (con controllo di arity) in Scala, usando impliciti di sovrapposizione con priorità. Il codice (~80 linee) è disponibile sotto forma di elenco here.Temo di essere un po 'trascinato e lo ho spiegato come un dettagliato post sul blog there.