让我们考虑生成随机数序列的问题,其约束条件是最终序列应该具有固定长度n并且前面/后面的元素应该是不同的(即邻居应该是不同的).我的第一个惯用方法是：
val seq = Stream.continually{ Random.nextInt(10) }
.foldLeft(Stream[Int]()){ (all: Stream[Int],next: Int) =>
if (all.length > 0 && all.last != next)
all :+ next
else
all
}
.take(n)
不幸的是,这不起作用,因为foldLeft试图消耗整个无限流,导致无限循环.直觉上并且根据this question我会预期这种行为仅适用于使用foldRight的解决方案？也许我只是错过了另一个惯用的解决方案？
解决方法
你可以使用这个技巧来自己压缩一个流：
def randSeq(n: Int): Stream[Int] = {
// an infinite stream of random numbers
val s = Stream.continually{ Random.nextInt(10) }
s.zip(s.tail) // pair each number with it sucessor
.filter((pair) => pair._1 != pair._2) // filter out equal pairs
.map(_._1) // break pairs again
.take(n); // take first n
}
然后你可以过滤掉连续的相等元素,最后得到所需的数量.
更新：是的,它会起作用.假设你有[1,2,3,…].压缩它将导致[(1,2),(2,3),(3,..),…],过滤产生[(1,…]所以最终的结果是[1,…].
我们甚至可以证明它：配对后,序列具有以下属性：a(i)._ 2 = a(i 1)._ 1.此属性在过滤步骤中保留.过滤步骤还确保a(i)._ 1！= a(i)._ 2.放在一起我们得到a(i)._ 1！= a(i)._ 2 = a(i 1)._ 1所以确实a(i)._ 1！= a(i 1)._ 1.
使用折叠的方法的问题在于您在折叠函数中自下而上构建Stream.这意味着为了评估流的头部,您必须评估无限序列的：操作,即使头部保持不变.必须从上到下构建适当的流 – 计算其头部并推迟其尾部的其余部分的计算.例如：
def randSeq1(n: Int): Stream[Int] = {
def g(s: Stream[Int]): Stream[Int] =
s match {
case h #:: t => h #:: g(t.dropWhile(_ == h))
}
g(Stream.continually{ Random.nextInt(10) }).take(n);
}
这里我们首先发出头部并将其余的计算推迟到懒惰评估的尾部.
