Secuencia con flujos en Scala

Question

Supongamos que hay una secuencia a[i] = f(a[i-1], a[i-2], ... a[i-k]). ¿Cómo se codificaría usando streams en Scala?

Answer 1

Se podrá generalizar para cualquier k, usando una matriz para a y otro parámetro k, y teniendo, f.i., la función con un parámetro 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) 

con el fin de tener el número 1000 hacen next.drop(1000)

Una actualización para mostrar cómo esto se podría hacer con varargs. Tenga en cuenta que no hay verificación de aridad para la función pasada:

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

Por desgracia, no se puede generalizar sobre el número y el tipo sea segura al mismo tiempo. Por lo que tendremos que hacer todo 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) 
    } 
    } 
} 

Y obtenemos 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))(_ + _ + _) 

... y hasta 22.

espero que el patrón se está clara alguna manera. (Por supuesto, podríamos mejorar e intercambiar la tupla initials con argumentos separados. Esto nos ahorra un par de paréntesis más adelante cuando lo usemos). Si algún día en el futuro llega el lenguaje de macro Scala, es de esperar que sea más fácil de definir.

Answer 3

¿Esto está bien? (a [i] = f (a [ik], a [i-k + 1], ... a [i-1]) en lugar de a [i] = f (a [i-1], a [i-2], ... a [ik]), ya que prefiero a esta forma)

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

Por ejemplo, el siguiente código para generar la secuencia de 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) 

El siguiente código puede generar una secuencia {an} donde 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 respuesta corta, que es probable que esté buscando, es un patrón para definir su Stream una vez que haya fijado un elegido k para la aridad de f (es decir, tiene un tipo fijo para f). El siguiente patrón le da un Stream que n -th element es el término a[n] de su secuencia:

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

(de crédito: es muy cerca de la answer de Andy Petrella, excepto que los elementos iniciales están configurados correctamente, y en consecuencia el rango en la Corriente partidos que en la secuencia)

Si desea generalizar más de k, esto es posible de forma segura (con comprobación de ariad) en Scala, utilizando implícitos superpuestos prioritarios. El código (~ 80 líneas) está disponible como una esencia here.Me temo que me dejé llevar un poco, y lo expliqué como una publicación detallada de & en el blog there.