Scala:生成固定长度序列的惯用方法(折叠无限流?)

Question

让我们考虑生成随机数序列的问题，约束条件是最终序列应具有固定长度的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试图消耗整个无限流，导致无休止的循环。直觉上，根据这个问题，我预计这种行为只适用于使用foldRight的解决方案？也许我只是错过了另一个惯用的解决方案？

Answer 1

您可以使用压缩流的技巧：

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,2,2,3,...]。压缩它将产生[(1,2),(2,2),(2,2),(2,3),(3,..),...]，过滤产生[(1,2),(2,3),(3,..),...]，所以最终结果是[1,2,3,...]。

我们甚至可以证明：配对后，序列具有以下性质：a(i)._2 = a(i+1)._1。此属性将保留在筛选步骤中。过滤步骤还确保CCD_。加在一起，我们得到了a(i)._1 != a(i)._2 = a(i+1)._1，所以实际上是a(i)._1 != a(i+1)._1。

---

使用fold的方法的问题在于，您在fold函数中构建了自下而上的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);
}

在这里，我们先发射头，然后将剩余的计算推迟到延迟求值的尾部。

Answer 2

我还没有检查过，但我希望你能明白：

@annotation.tailrec 
def rndDistinctItems(n: Int, xs: List[Int] = Nil): List[Int] = if (n > 0) {
    val next = Random.nextInt(10)
    val shouldTryAgain = xs != Nil && next == xs.head
    if (shouldTryAgain) rndDistinctItems(n, xs)
    else rndDistinctItems(n - 1, next::xs)
} else xs

Answer 3

虽然用自己的头压缩流是一个非常好的技巧，但我更喜欢sliding运算符：

val s = Stream.continually { Random.nextInt(10) } sliding(2) collect { case Stream(a,b) if a!=b => a } take 100 

小心：你得到的是一个迭代器，而不是一个流。流存储其结果（因此可以多次迭代）。迭代器可能只能迭代一次。

Answer 4

那么，这个怎么样：

scala> val M = 10
M: Int = 10
scala> val seq = Stream.iterate(Random.nextInt(M)){ x => 
         val nxt = Random.nextInt(M-1); if(nxt >= x) nxt + 1 else nxt 
       }