scala - 我发现自己在大多数函数结束时反转累加器；我怎么能停下来？

Question

我一直在写一本关于 Scala 函数式编程的书(正名)。通过练习，我发现自己经常在用累加器收集最终结果时反转我的最终结果。我记得在我的 Racket 时代也有类似的模式。我担心的是我可能会使我的代码比必要的稍微困惑，并且可能会执行额外的 O(n)操作(其中 n 是累加器/结果的长度。)

例子:

// Produces a List from a Stream, forcing evaluation of all elements.
def toList(): List[A] = {
    def go(l: Stream[A], acc: List[A]): List[A] = {
        l match {
            case Empty if acc.nonEmpty => acc.reverse
            case Empty if acc.isEmpty => Nil
            case Cons(h, t) => go(t(), h() :: acc)
        }
    }
    // "this" is a Stream[A].
    go(this, Nil)
}

这种颠倒结果以恢复原始顺序的模式是我所关心的。有没有更好的方法(没有 reverse 调用)在 FP 中，特别是在 Scala 中做到这一点？

Answer 1

您可以尝试使用诸如 Vector 之类的数据结构，它会在有效的恒定时间附加一个值。

所以你有:

case Cons(h, t) => go(t(), h() :: acc)

改用:

case Cons(h,t) => go(t(), acc :+ h())

然后当您返回累加器时不需要反向。