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

发布时间：2020-12-16 18:04:17 所属栏目：安全来源：网络整理

导读：让我们考虑生成随机数序列的问题,其约束条件是最终序列应该具有固定长度n并且前面/后面的元素应该是不同的(即邻居应该是不同的).我的第一个惯用方法是： val seq = Stream.continually{ Random.nextInt(10) } .foldLeft(Stream[Int]()){ (all: Stream[Int],n

让我们考虑生成随机数序列的问题,其约束条件是最终序列应该具有固定长度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);
}

这里我们首先发出头部并将其余的计算推迟到懒惰评估的尾部.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!