scala - 帮助改写函数式风格

Question

我正在学习 Scala 作为我的第一个函数式语言。作为问题之一，我试图找到一种生成最多 n 个位置的序列 S 的功能方法。 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

到目前为止，Pavel 的答案最接近，但效率也很低。两个flatMap s 和 zipWithIndex这里是矫枉过正:)

我对所需输出的理解:

结果包含所有正整数(从 1 开始)至少一次

每个号码n出现在输出 (n/2) + 1 中次

正如 Pavel 正确指出的，解决方案是从 Stream 开始。然后使用 flatMap :

Stream from 1

这会生成一个 Stream ，一个潜在的永无止境的序列，只根据需要产生值。在这种情况下，它生成 1, 2, 3, 4...一直到 Infinity(理论上)或 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)从冷启动会很慢! (与您的命令式算法共享的问题)。如果您需要这样做，那么到目前为止所有的解决方案都不可能适合您。