我发现自己在大多数功能结束时都会反转累加器; 我该怎么办？

Question

我一直在写一本关于Scala中的函数式编程的书(有这个标题.)通过练习,我发现自己经常在用累加器收集时反转我的最终结果.我记得在我的球拍日期间有类似的模式.我担心的是,我可能会使我的代码比必要的稍微麻烦,并且可能执行额外的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())

然后在返回累加器时不需要反转.