Sekwencja ze strumieniami w Scali

Question

Załóżmy, że istnieje sekwencja a[i] = f(a[i-1], a[i-2], ... a[i-k]). Jak mógłbyś zakodować go przy użyciu streams w Scali?

Answer 1

Będzie można go uogólnić dla dowolnego k, używając tablicy dla a i innego parametru k i mając, np., Funkcję z parametrem 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) 

w celu uzyskania 1000. zrobić next.drop(1000)

powiadomienie, aby pokazać w jaki sposób można to zrobić z varargs. Pamiętaj, że nie ma kontroli arity dla funkcji przeszły:

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

Niestety, nie możemy generalizować na liczbę i pewności jednocześnie typ. Więc będziemy musieli zrobić to ręcznie:

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

i otrzymujemy 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))(_ + _ + _) 

... i aż do 22.

Mam nadzieję, że wzór staje się jasne, jakoś. (Moglibyśmy oczywiście poprawić i wymienić krotkę initials z oddzielnymi argumentami, co pozwala nam zaoszczędzić parę nawiasów później, kiedy go użyjemy.) Jeśli pewnego dnia w przyszłości pojawi się język makr Scala, to mam nadzieję, że będzie łatwiej zdefiniować.

Answer 3

Czy to jest w porządku? (a [i] = f (a [ik], a [i-k + 1], ... a [i-1]) zamiast a [i] = f (a [i-1], a [I-2] ... A [ik]), ponieważ ten sposób raczej)

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

na przykład, następujące kodu do generowania Fibonacciego.

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) 

Następujący kod generuje sekwencję {a} gdzie A1 = 1, a2 = 2, a3 = 3, a (n + 3) = a (n) + 2 a (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

krótka odpowiedź, że jesteś prawdopodobnie szuka, to wzór zdefiniować Stream po rozwiązaniu wybrana k na liczbę operandów f (czyli masz stały typ dla f. Następujący wzór daje ci Stream, który jest -ty element jest terminem a[n] twojej sekwencji:

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

(kredyt: to jest bardzo blisko do answer Andy Petrella, chyba że początkowe elementy są ustawione prawidłowo, a co za tym idzie pozycja w Strumieniu odpowiada, że ​​w sekwencji)

Jeśli chcesz generalizować ponad k, jest to możliwe w bezpieczny sposób (z kontrolą jasności) w Scali, stosując priorytetowe nakładające się implikacje. Kod (~ 80 linii) jest dostępny jako powód here.Obawiam się, że trochę mnie porwał i wyjaśniłem, że jest to szczegółowy & długi wpis na blogu there.