函数式编程风格的重写帮助

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循环的情况下编写此代码。

谢谢！

- Aaron Yodaiken

---

我只是稍微了解一下Scala，但是像这样的代码应该可以帮助你入门：Stream.continually(x).take(S(x)).toList。编写一个递归函数，并将其作为定义的一部分 - 我只是不太了解Scala，无法告诉你它应该是什么。 - erisco

你确定这个序列是唯一的吗？我认为 1, 0, 0, 0, ... 也符合你的条件。 - Jus12

看起来是Golomb序列：http://oeis.org/A001462 - Landei

Answer 1

Pavel的答案目前为止是最接近要求的，但也不够高效。两个flatMap和一个zipWithIndex在这里是过度的 :)

我对所需输出的理解：

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

正如Pavel所指出的那样，解决方案是从一个Stream开始，然后使用flatMap：

Stream from 1

这会生成一个Stream，它是一种潜在的无限序列，只有在需要时才会产生值。在这种情况下，它生成从1, 2, 3, 4...一直到理论上的无穷大（实际上是Integer.MAX_VALUE）。

Stream可以像其他集合一样进行映射。例如：(Stream from 1) map { 2 * _ }会生成一个偶数流。

您还可以在Stream上使用flatMap，允许您将每个输入元素映射到零个或多个输出元素；这对解决问题非常关键：

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

所以…这是如何工作的？对于元素3，lambda表达式{ n => Stream.fill(n/2 + 1)(n) }将产生输出流3,3。对于前五个整数，你会得到：

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) 将会很慢！（这是与你的命令式算法共享的问题）。如果您需要这样做，那么迄今为止没有一个解决方案可能适合您。

- Kevin Wright

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)

你可以查看我的文章，了解如何以函数式风格处理数字序列的更多示例。

- Pavel Fatin

---

正如Kevin所指出的那样，在重构后的代码段中有两个flatMap和一个zipWithIndex过多了。此外，Stream也是过度的，因为计算没有引用以前计算的值。因此，“def it = Iterator.from(1).flatMap(n => Iterator.fill(n/2 + 1)(n))”是更有效的重构。然而，重构不足以产生正确的Golomb序列。第二个代码片段使用递归关系的流来实现目标。 - Pavel Fatin

如果我没记错的话，在重构后的版本中仍然需要一个Stream，因为Iterator没有提供flatMap操作。不过我可能在这一点上是错误的（在我的手机上检查并不容易，scaladoc不太适合触摸屏）。 - Kevin Wright

@Kevin Iterator确实具有flatMap方法。 - Pavel Fatin

Answer 3

这是一个Scala新手的尝试。请记住，我并不真正理解Scala，也不真正理解问题，也不真正理解你的算法。

def genX_Ys[A](howMany : Int, ofWhat : A) : List[A] = howMany match {
    case 1 => List(ofWhat)
    case _ => ofWhat :: genX_Ys(howMany - 1, ofWhat)
}

def makeAtLeast(startingWith : List[Int], nextUp : Int, howMany : Int, minimumLength : Int) : List[Int] = {
    if (startingWith.size >= minimumLength) 
      startingWith 
    else 
      makeAtLeast(startingWith ++ genX_Ys( howMany, nextUp), 
                 nextUp +1, howMany + (if (nextUp % 2 == 1) 1 else 0), minimumLength)
}

def genSequence(numItems: Int) =  makeAtLeast(List(1), 2, 2, numItems).slice(0, numItems)

这似乎能够工作，但请再次阅读上述注意事项。特别是，我确定有一个库函数可以执行genX_Ys，但我找不到它。

编辑可能是

def genX_Ys[A](howMany : Int, ofWhat : A) : Seq[A]  = 
   (1 to howMany) map { x => ofWhat }

- Michael Lorton

---

你要找的库函数是 List.fill。 - Kevin Wright

Answer 4

这是您的代码转换为更具功能性风格的翻译：

def genSequence(numItems: Int): List[Int] = {
  genSequenceR(numItems, 2, 2, 0, 1, List[Int](1))
}


def genSequenceR(numItems: Int, seq_no: Int, no:Int, no_nos: Int, numMade: Int, list: List[Int]): List[Int] = {
 if(numMade < numItems){
   if(no_nos < seq_no){
     genSequenceR(numItems, seq_no, no, no_nos + 1, numMade + 1, list :+ no)
   }else if(no % 2 == 0){
     genSequenceR(numItems, seq_no, no + 1, 0, numMade, list)
   }else{
     genSequenceR(numItems, seq_no + 1, no + 1, 0, numMade, list)
   }
  }else{
    list
  }
}

genSequenceR是一个递归函数，它在列表中累积值并根据条件调用具有新值的函数。与while循环类似，当numMade小于numItems时终止，并将列表返回给genSequence。

这是您代码的相当基本的函数式翻译。它可以改进，通常有更好的方法。我建议尝试使用模式匹配来改进它，然后朝着在此处使用Stream的其他解决方案努力。

- Brian

Answer 5

这是Golomb序列定义的非常直接的“翻译”：

val it = Iterator.iterate((1,1,Map(1->1,2->2))){ case (n,i,m) =>
    val c = m(n)
    if (c == 1) (n+1, i+1, m + (i -> n) - n)
    else (n, i+1, m + (i -> n) + (n -> (c-1)))
}.map(_._1)

println(it.take(10).toList)

tripel（n，i，m）包含实际数字n，索引i和一个Map m，其中包含n必须重复的次数。当我们n的计数器在Map中达到1时，我们增加n（并可以从Map中删除n，因为它不再需要），否则我们只是减少n在Map中的计数器并保持n。在任何情况下，我们都将新的i-> n对添加到Map中，稍后将用作计数器（当后续n达到当前i的值时）。

[编辑]

思考一下，我意识到我不需要索引甚至不需要查找（因为“计数器”已经按“正确”的顺序排列），这意味着我可以用队列替换Map：

import collection.immutable.Queue

val it = 1 #:: Iterator.iterate((2, 2, Queue[Int]())){
  case (n,1,q) => (n+1, q.head, q.tail + (n+1))
  case (n,c,q) => (n,c-1,q + n)
}.map(_._1).toStream

当从2开始时，迭代器可以正常工作，因此我不得不在开头添加1。第二个元组参数现在是当前n的计数器（取自队列）。当前计数器也可以保存在队列中，这样我们只有一对，但由于复杂的队列处理，这样做就不太清晰了：

val it = 1 #:: Iterator.iterate((2, Queue[Int](2))){
  case (n,q) if q.head == 1 => (n+1, q.tail + (n+1))
  case (n,q) => (n, ((q.head-1) +: q.tail) + n)
}.map(_._1).toStream 

- Landei