根据元素的值添加到列表第 n 次

Question

我想编写一个函数，将一个元素 n 添加到列表中 n 次，用于输入列表中的所有元素。

例如：

L = List(2,4,1)

输出应该是：

List(2,2,4,4,4,4,1)

我想用尾递归来做。到目前为止，我已经写了这个：

 def repeat(numbers: List[Int]): List[Int] = {
     def repeat_acc(numbers: List[Int], acc: List[Int], number_acc: Int): List[Int] = {
        if (numbers.length == 0)
           return acc
        else if (number_acc == 0)
             repeat_acc(numbers.tail, acc, numbers.head)
        else
             repeat_acc(numbers, acc :+ numbers.head, (number_acc-1))
        }
        repeat_acc(numbers, List(), 0)
 }

问题是它遗漏了列表的第一个元素。对于此输出将是：

(4, 4, 1, 1, 1, 1)

我知道为什么会这样，但我无法修复它。我尝试了很多其他方法，但对我来说，尾递归似乎在这里不起作用。有的老是出错，我就得到了错误的结果

感谢任何建议。

Answer 1

我知道您想进行个性化的尾递归调用，但我建议改为：

def repeat(numbers: List[Int]): List[Int] = {
    numbers.flatMap(n => List.fill(n)(n))
}

内部函数取值n并在列表中重复n次，然后将这个函数平映射到原始列表上（常规映射会将List(1,2,3)变成List(List(1), List(2, 2), List(3, 3, 3))，所以我们使用平面地图）。这具有 'doing it the Scala way' 的优势，内置 collections 功能。

Answer 2

好的，我找到了解决方案。看起来很糟糕，但有效。我太累了，想不出更好的东西。

这是我的代码：

  def repeat(numbers: List[Int]): List[Int] = {
     def repeat_acc(numbers: List[Int], acc: List[Int], number_acc: Int): List[Int] = {
        if (numbers.length == 1 && number_acc == 0)
           return acc
        else if (acc.length == 0)
            repeat_acc(numbers, acc :+ numbers.head, (number_acc-1))
        else if (number_acc == 0 && numbers.tail != Nil ){
           repeat_acc(numbers.tail, acc, (numbers.tail.head))
        }
        else
           repeat_acc(numbers, acc :+ numbers.head, (number_acc-1))

        }
           repeat_acc(numbers, List(), numbers.head)

  }

Answer 3

如果您向内部递归方法添加另一个参数，代表当前添加的数字，这个问题会变得简单得多。您还应该熟悉 match 语句，因为它们在 Scala 中非常强大，可以帮助准确表达这种类型的逻辑。嵌套的 if/else 语句和早期的 return 语句被认为是单一的。尝试：

def repeat(numbers: List[Int]) = {
    def repeatAcc(acc: List[Int], curr: Int, rem: Int, numbers:List[Int]): List[Int] = 
        (numbers, rem) match {
            case (Nil, 0) => acc
            case (hd::tl, 0) => repeatAcc(acc, hd, hd, tl) 
            case (_, n) => repeatAcc(acc :+ curr, curr, n - 1, numbers)  
    }

    repeatAcc(List.empty[Int], 0, 0, numbers)
}

您也可以尝试使用一些标准的 Scala 方法，例如 List.fill，它可以与尾递归结合使用，如下所示：

def repeat(numbers: List[Int]) = {
    def repeatAcc(acc: List[Int], numbers:List[Int]): List[Int] = numbers match {
        case hd::tl => repeatAcc(acc ++ List.fill(hd)(hd), tl)  
        case Nil => acc
    }

    repeatAcc(List.empty[Int], numbers)
}

最后，我了解到您正在尝试了解这些核心概念，但应该指出的是，使用 Scala 内置插件这非常简单：

(List.empty[Int] /: numbers) { case (soFar, next) => soFar ++ List.fill(next)(next) }

numbers.flatMap(x => List.fill(x)(x))

Answer 4

简单，就用fill + flatMap

val result = L.flatMap(x => List.fill(x)(x))

对于递归解决方案：

scala>  def repeat(numbers: List[Int]): List[Int] = {
  def run(nums:List[Int]):List[Int] ={
  nums match {
  case Nil => List.empty[Int]
  case x::Nil => List.fill(x)(x)
  case x::xs => List.fill(x)(x):::run(xs)
  }}
  run(numbers)
  }

scala> repeat(List(2,4,1))
res1: List[Int] = List(2, 2, 4, 4, 4, 4, 1)

Answer 5

试试这个，它有效

import scala.annotation.tailrec
@tailrec
def f(l: List[Int], res: List[Int] = Nil): List[Int] = {

  @tailrec
  def g(n: Int, acc: List[Int]): List[Int] = {
        if (n == 1) acc
        else g(n - 1, acc :+ acc.head)
    }

if (l == Nil) res else f(l.tail, res ++ g(l.head, List(l.head)))
}

scala> f(List(1,2,3))
res0: List[Int] = List(1, 2, 2, 3, 3, 3)

根据元素的值添加到列表第 n 次

Add to list nth times depending of element's value

scala

tail-recursion