Последовательность с потоками в Scala

Question

Предположим, что существует последовательность a[i] = f(a[i-1], a[i-2], ... a[i-k]). Как бы вы закодировали его, используя streams в Scala?

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) 

для того, чтобы иметь сделать next.drop(1000) 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 с отдельными аргументами. Это поможет нам скопировать скобки позже, когда мы его используем.) Если в будущем наступит маска-язык Scala, это, надеюсь, будет легче определить.

Answer 3

В порядке? (a [i] = f (a [ik], a [i-k + 1], ... a [i-1]) вместо a [i] = f (a [i-1], a [я-2] ... а [ик]), так как я предпочитаю таким образом)

/** 
    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, а3 = 3, а (п + 3) = а (п) + 2а (п + 1) + 3a (п + 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 как только вы закрепили избранный k для арности f (т.е. у вас есть фиксированный тип для f). Следующая диаграмма дает вам 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)) 

(кредит: это очень близко к answer Энди Петрелла, за исключением того, что начальные элементы установлены правильно, и, следовательно, ранг в потоке соответствует таковому в последовательности)

Если вы хотите обобщить более k, это возможно безопасным способом (с проверкой arity) в Scala, используя приоритетные перекрывающиеся импликации. Код (~80 строк) доступен как gist here.Боюсь, я немного увлекся и объяснил это как подробный & блог блога there.