帮助重写功能风格

Question

我正在学习Scala作为我的第一个功能性语言.作为其中一个问题,我试图找到一种生成序列S到n个位置的功能性方法.定义S使得S(1)= 1,并且S(x)= x出现在序列中的次数.(我不记得这是什么,但我之前在编程书中看过它.)

在实践中,序列如下所示:

  S = 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7 ...

我可以使用像这样的命令式样式在Scala中很容易地生成这个序列:

  def genSequence(numItems: Int) = {
    require(numItems > 0, "numItems must be >= 1")
    var list: List[Int] = List(1)
    var seq_no = 2
    var no     = 2
    var no_nos = 0
    var num_made = 1

    while(num_made < numItems) {
      if(no_nos < seq_no) {
        list = list :+ no
        no_nos += 1
        num_made += 1
      } else if(no % 2 == 0) {
        no += 1
        no_nos = 0
      } else {
        no += 1
        seq_no += 1
        no_nos = 0
      }
    }
    list
  }

但我真的不知道如何在不使用vars和while循环的情况下编写它.

谢谢!

Answer 1

到目前为止,帕维尔的答案最接近,但效率也很低.两个flatMaps和一个zipWithIndex在这里是矫枉过正:)

我对所需输出的理解:

• 结果包含所有正整数(从1开始)至少一次
• 每个数字都n出现在输出(n/2) + 1时间中

正如Pavel正确指出的那样,解决方案是从一开始Stream就使用flatMap:

Stream from 1

这会生成一个Stream可能永无止境的序列,只能按需生成值.在这种情况下,它一直生成1, 2, 3, 4...无限(理论上)或Integer.MAX_VALUE(实际上)

与任何其他集合一样,可以映射流.例如:(Stream from 1) map { 2 * _ }生成偶数流.

您还可以flatMap在Streams上使用,允许您将每个输入元素映射到零个或多个输出元素; 这是解决问题的关键:

val strm = (Stream from 1) flatMap { n => Stream.fill(n/2 + 1)(n) }

那么......这是如何运作的？对于元素3,lambda { n => Stream.fill(n/2 + 1)(n) }将生成输出流3,3.对于前5个整数,您将获得:

1 -> 1
2 -> 2, 2
3 -> 3, 3
4 -> 4, 4, 4
5 -> 5, 5, 5
etc.

因为我们正在使用flatMap,所以这些将被连接起来,产生:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, ...

流被记忆,因此一旦计算出给定值,它将被保存以供将来参考.但是,所有前面的值必须至少计算一次.如果你想要完整的序列,那么这不会导致任何问题,但它确实意味着S(10796)从冷启动生成将是缓慢的!(与您的命令式算法共享的问题).如果您需要这样做,那么到目前为止,没有一个解决方案可能适合您.

Answer 2

以下代码生成与您的完全相同的序列:

val seq = Stream.from(1)
        .flatMap(Stream.fill(2)(_))
        .zipWithIndex
        .flatMap(p => Stream.fill(p._1)(p._2))
        .tail

但是,如果要生成Golomb序列(符合定义,但与示例代码结果不同),则可以使用以下内容:

val seq = 1 #:: a(2)
def a(n: Int): Stream[Int] = (1 + seq(n - seq(seq(n - 2) - 1) - 1)) #:: a(n + 1)

您可以查看我的文章,了解如何处理函数式数字序列的更多示例.