Think

实现尾递归的右折叠

题目概述

折叠，也称为归约（reduce）、积累（accumulate）、聚集（aggregate）、压缩（compress）或注入（inject），指称一组高阶函数，它们分析递归数据结构并通过使用给定组合运算，将递归的处理它的构成部件、建造一个返回值的结果重组起来。典型的，要向折叠提供一个组合函数，一个数据结构的顶端节点，和可能的在特定条件下使用的某些缺省值。折叠接着以系统性方式使用这个函数，进行组合这个数据结构的层级中的元素 – By wiki

下面的Scala代码定义了右折叠。因为不是尾递归的函数，无法应用对应优化，在as很大的时候会造成Stack-Overflow。我们需要探索stack-safe的实现。

1
2
3
4
5
def foldRight[A, B](as: List[A], z:B)(f: (A, B) => B): B =
    as match {
        case Nil => z
        case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }

解题报告

注意到，实现尾调用的foldLeft是很trivial的，有没有什么办法利用foldLeft呢？

1
2
3
4
5
def foldLeft[A, B](as: List[A], z:B)(f: (B, A) => B): B =
    as match {
        case Nil => z
        case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
    }

一个朴素的想法是借助reverse通过foldLeft实现foldRight，如果reverse是stack-safe的，且foldLeft也是stack-safe的，那么我们就有了stack-safe的foldRight实现。代码如下：

1
2
3
4
5
def foldRightViafoldLeft_1[A, B](as: List[A], z:B)(f: (A, B) => B): B =
    list.reverse().foldLeft(z)((b, a) => f(a, b))

def reverse[A](as: List[A]): [A] =
    as.foldLeft(List.empty[Int])((b, a) => a::b)

Hard：如果不使用reverse呢？首先我们先观察以下例子，对于list: [1, 2, 3]:

1
2
foldLeft(list, z)(f) ==> f(f(f(z, 1), 2), 3)
foldRight(list, z)(g) ==> g(1, g(2, g(3, z)))

第一阶段：对于两个结果如果实现互换，那么f和g的映射中有文章。foldLeft和foldRight是否可以逐步转换？

1
2
3
f(z, 1) ==> g(1, z)
f(g(1, z), 2) ==> g(1, g(2, z))
...

第二阶段：如果z是一个computed value我们很难做到这一点，但如果是一个function呢？也就是：

1
2
3
z => f(z, 1) ==> z => g(1, z)  // z => f(z, 1) 与 f(identity[B], 1) 等价
z => f(g(1, z), 2) ==> z => g(1, g(2, z))
...

第三阶段：令z:B，我们可以定义f为：

1
2
3
令 f(a: A, b: B): B 
def h(g: B => B, b: A): B => B =
    x:B => g(f(b, x))

最后阶段：我们可以利用foldLeft做文章，令f(a: A, b: B): B; foldLeft(list, b:B => b)((g, a) => x => g(f(a, x)))将产生一个function，其signature为B => B。然后我们对其apply初始值就能满足最终要求:

1
2
def foldRightViafoldLeft_2[A, B](as: List[A], z:B)(f: (A, B) => B): B =
    as.foldLeft((b: B) => b)((g, a) => x => g(f(a, x)))(z)

可以跟朴素实现对比观察，可以看出来规律：

1
2
3
4
5
def foldRightViafoldLeft_1[A, B](as: List[A], z:B)(f: (A, B) => B): B =
    list.reverse().foldLeft(z)((b, a) => f(a, b))

def reverse[A](as: List[A]): [A] =
    as.foldLeft(List.empty[Int])((b, a) => a::b)

其实foldRightViafoldLeft_2与foldRightViafoldLeft_1思路一致，都是要同时调换f的运算顺序和列表顺序。foldRightViafoldLeft_2通过构造function而不是computed value将两个对调放在一起了。两个函数在compose的时候，外层的函数后计算，内层的先计算。再结合currying，不断partial apply并compose，就能得到与朴素实现一模一样的结果。