在Scala中使用流进行序列操作

Question

在Scala中使用流进行序列操作

scalastream

5

假设有一个序列 a[i] = f(a[i-1], a[i-2], ... a[i-k])。你如何使用Scala中的streams编写它的代码？

- Michael

2

我正在尝试理解序列的规则。k是什么？a[0]（流中的第一个元素）是什么？a[1]是什么？ - toddsundsted

假设我已经知道序列的前k个元素：a[0]，a[1]，...，a[k-1]。现在我想使用函数f计算n > k的a[n]。 - Michael

4个回答

3

这样做可以吗？(a[i] = f(a[i-k], a[i-k+1], ... a[i-1]) 而不是 a[i] = f(a[i-1], a[i-2], ... a[i-k])，因为我更喜欢这种方式)

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

- Eastsun

3

简单来说，你可能正在寻找的答案是一种模式，可以在为 f 的元数（即，您已经固定了 f 的类型）选择一个 k 后定义您的 Stream。以下模式可为您提供一个 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的答案，只是初始元素被正确设置，因此Stream中的排名与序列中的排名相匹配)

如果您想泛化k，则可以在Scala中以类型安全的方式（具有数量检查）使用优先重叠的隐式。该代码（约80行）可作为gist在这里获得。恐怕我有点过分了，并将其解释为详细和冗长的博客文章在那里。

- Francois G

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

And we get 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宏语言，这将更容易定义。

- Debilski

嗯，def 应该改成 lazy val。 - Debilski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Petrella · Accepted Answer

可以使用一个a数组和另一个k参数来概括任何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)。

以下是使用可变参数的更新示例。请注意，传递的函数没有元数检查：

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)

}