Последовательность с потоками в Scala - PullRequest
Новая
       7

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

5 голосов
/ 27 декабря 2011

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

Ответы [ 4 ]

3 голосов
/ 02 января 2012

Краткий ответ, который вы, вероятно, ищете, - это шаблон для определения вашего 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))

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

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

3 голосов
/ 28 декабря 2011

Это нормально?(a [i] = f (a [ik], a [i-k + 1], ... a [i-1]) вместо a [i] = f (a [i-1], a [i-2], ... a [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)

Следующий код может генерировать последовательность {an}, где 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)
3 голосов
/ 27 декабря 2011

Можно будет обобщить его для любого k, используя массив для a и другой параметр k и, например, функцию с параметром 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)

чтобы 1000-й сделать next.drop(1000)

Обновление, показывающее, как это можно сделать с помощью varargs. Остерегайтесь того, что для переданной функции нет проверки арности: 

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)

}

2 голосов
/ 27 декабря 2011

К сожалению, мы не можем обобщать числа и быть одновременно безопасными.Так что нам придется все это делать вручную: 

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, надеюсь, это будет легчеопределить.

...