题目概述
折叠,也称为归约(reduce)、积累(accumulate)、聚集(aggregate)、压缩(compress)或注入(inject),指称一组高阶函数,它们分析递归数据结构并通过使用给定组合运算,将递归的处理它的构成部件、建造一个返回值的结果重组起来。典型的,要向折叠提供一个组合函数,一个数据结构的顶端节点,和可能的在特定条件下使用的某些缺省值。折叠接着以系统性方式使用这个函数,进行组合这个数据结构的层级中的元素 – By wiki
下面的Scala
代码定义了右折叠。因为不是尾递归的函数,无法应用对应优化,在as很大的时候会造成Stack-Overflow。我们需要探索stack-safe的实现。
1 | def foldRight[A, B](as: List[A], z:B)(f: (A, B) => B): B = |