scala - 如何在 Scala 中为列表实现自定义尾递归映射

Question

我想实现一个名为 map 的函数，它接收一个列表和一个函数，并产生将函数应用于输入列表的每个元素的结果。
所以到目前为止我有这个:

def map(list: List[Int], function: (Int) => Int): List[Int] = {
  def loop(list: List[Int], acc: List[Int]): List[Int] = {
    list match {
      case Nil => acc
      case head :: tail => loop(list.tail, function(head) :: acc)
    }
  }
  loop(list.reverse, Nil)
}

这段代码有效并给了我预期的结果，但我不禁想到有一种更优雅、更有效的方法，不涉及使用 reverse或其他不是 head 的列表方法或 tail .

Answer 1

至于滚动您自己的纯功能实现map函数，不使用任何可变状态或内置 List高阶函数，你做得很好!不得不reverse该列表似乎没有必要，但它是值得的，因为添加到列表是一种非常有效的操作。

除了评论中建议的其他方法外，您还可以使用 acc一个 scala.collection.mutable.ListBuffer (它支持高效的追加和前置操作)，然后在完成后将其转换为列表。然而，转换过程并没有比 reverse 有很大的改进。 .

否则，您可以做一些小事来改善您的 map功能:

通过使用柯里化(Currying)参数，您可以使用 map更优雅。

需要尾递归的函数应该总是用 scala.annotation.tailrec 修饰。属性。 Scala 编译器会知道你的意图，如果函数无法优化以使用尾递归，则会发出错误。

使这个函数通用化是微不足道的，这将使它更广泛地有用。

执行 reverse 通常更惯用。对结果进行操作。这对 map 操作没有任何影响，但是如果您要编写过滤器操作，例如，反转可能更小的过滤元素集会更有效。

这就是它的样子:

import scala.annotation.tailrec

def map[A, B](list: List[A])(function: (A) => B): List[B] = {

  @tailrec
  def loop(rem: List[A], acc: List[B]): List[B] = rem match {
    case Nil => acc.reverse
    case head :: tail => loop(tail, function(head) :: acc)
  }
  loop(list, Nil)
}