帮助以函数式风格重写

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

以下是将代码转换为更实用的风格：

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 的其他解决方案。

Answer 2

这是 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 }

Answer 3

这是哥伦布数列定义的非常直接的“翻译”：

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)

三元组 (n,i,m) 包含实际数字 n、索引 i 和 Map m，其中包含 n 必须重复的频率。当映射中 n 的计数器达到 1 时，我们增加 n（并且可以从映射中删除 n，因为不再需要它），否则我们只需减少映射中 n 的计数器并保留 n。在每种情况下，我们都会添加新的对 i -> n 进入映射，稍后将用作计数器（当后续 n 达到当前 i 的值时）。

[编辑]

考虑一下，我意识到我不需要索引，甚至不需要查找（因为“计数器”已经处于“正确”的顺序），这意味着我可以替换带队列的映射：

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 

Answer 4

到目前为止，帕维尔的答案最接近，但效率也很低。两个 flatMap 和一个 zipWithIndex 在这里是多余的:)

我对所需输出的理解：

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

正如 Pavel 正确指出的，解决方案是从 Stream 开始，然后使用 < code>flatMap：

Stream from 1

这会生成一个Stream，这是一个可能永无止境的序列，仅根据需要生成值。在本例中，它生成 1, 2, 3, 4... 一直到 Infinity（理论上）或 Integer.MAX_VALUE（实际上）

Streams 可以与任何其他集合一样被映射。例如：(Stream from 1) map { 2 * _ } 生成偶数的 Stream。

您还可以在 Streams 上使用 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。对于前 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 5

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

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)

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