探索与理解Folds：借助GHCi提升Haskell编程体验

抽象归纳的艺术：Folds的奥秘

在Haskell中实现Folds可能是一项棘手且让人头疼的任务，尤其是在处理Template Haskell时。当面对不那么直观的关联性和严格性问题时，Folds往往让人感到困惑。然而，随着错误和重试，我们可能会忽视一些微妙的细节，例如错误地选择了一个左折叠而忽视了实际上更适合右折叠的需求。现在，有了更系统的方法来引导我们，这一切都将变得轻松起来。

利用GHCi，让Folds不再难解

我的同事Patrick向我介绍了如何结合基本的启发式方法和GHCi（Haskell交互式环境）来进行结构化的实践，以消除在理解和应用Folds过程中的认知负担。这是一种游戏规则改变者的方法，能帮助那些在Haskell世界里迷失方向的新手更好地驾驭Folds。

目录

1. 什么是Folds
2. 简单示例
3. Folds的优缺点
4. 系统化选择Folds的方法

了解Folds

这里不会深入解释Folds的基础知识，你可以参考这个维基页面获取更多信息。本文的重点是展示如何确定何时选择哪种Folds来适应你的需求。

简单定义

Folds是一组高阶函数，它们作用于可以被“折叠”的数据结构（如列表、树等），并将其转化为另一种数据结构或最终结果。这些功能是Foldable类型类的一部分。

抽象递归行为

在列表和类似列表的数据结构上表达递归操作时，经常出现的功能共享类似的模式：首先定义空列表的边缘情况，然后考虑一个元素的情况，接着用(x:xs)模式处理剩余的元素。递归步骤通常是应用于xs，即剩余的列表元素。这种共同的行为已经被提取出来，形成了我们现在所说的Folds！

不同类型的Folds

Foldable类提供了多种不同的fold函数，具有相似但微妙区别的定向和行为：

高阶函数	描述
foldl:	从左侧开始，带着一个组合函数和初始值向右移动。这对于无限列表来说是个坏消息，因为会导致非终止状态。
foldr:	从右侧开始，带着一个组合函数和初始值向左移动。对于无限列表可正常终止。
foldl1:	类似foldl，但不需要显式提供起始值。它假设列表的第一个元素为起始值，然后从下一个元素开始折叠。要求输入非空，否则会抛出异常。
foldr1:	类似foldl1，默认起始值为最后一个元素，并向左移动。要求输入非空，否则会抛出异常。
foldl':	类似foldl，但在累加器中是严格的。

简单示例：从手动递归到Folds

在学习如何利用GHCi选择正确的Folds之前，先要理解如何将手动递归转换为fold操作。

将手动递归转换成fold

作为简单的练习，让我们用Folds重构一个小学级别的函数——求和。

使用手动递归的求和

我们希望计算列表[1,2,3,4,5]的所有值之和。

如果编写一个常规的递归函数，定义可能如下：

sumManual :: Num a => [a] -> a
sumManual [] = 0
sumManual (x:xs) = x + sumManual xs

这个函数在ghci中工作正常：

> sumManual [1,2,3,4,5]
15

foldl的定义包含了驱动手动递归所需的所有机械结构：

foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs

这意味着我们可以把foldl直接用于sum实现：

sumFold :: Num a => [a] -> a
sumFold = foldl (+) 0

测试一下：

> sumFold [1,2,3,4,5]
15

Folds的利与弊

Folds的优点

• **维护性：**抽象掉递归部分允许我们将“做什么”与“怎么做”分离开，使递归逻辑不再直接暴露在代码中。我们关注的是函数的目的，而不是如何实现递归，减少了潜在的错误源。
• **性能：**GHC倾向于内联foldl'和foldr，而不内联手动编写的递归代码。此外，使用fold操作可以使性能问题更加明显，因为我们可以在独立于其递归实现的情况下检查函数的性能。
• **通用性：**Folds适用于任何容器类型，这为我们提供了更一般的表达方式，然后可以根据具体的容器进行特化。

Folds的缺点

• **阅读困难：**虽然有诸多好处，但Folds也可能带来额外的认知负荷。它们为简洁的逻辑增添了复杂性，递归部分现在变得更加晦涩。分离关注点通常是一种有用的设计策略，但过多的层次也可能是问题。
• **编写困难：**写出正确的fold也很困难。通常很难判断应使用左折叠还是右折叠，以及是否需要提供初始值。
• **性能：**fold天生具有O(n) * fold_function_complexity的时间复杂度。理想情况下，fold的每个步骤应该是O(1)、O(log n)或其他次线性时间复杂度，因此在某些情况下fold可能会加速，而在其他情况下可能会损害性能。

结构化选择Folds的方法

使用Folds的大致流程：

1. 理解要实现的函数类型签名，这将指导你处理哪些数据结构，期望产生什么输出。
2. 可选步骤：思考如何将该功能表示为显式函数（这一步骤可以省略，但我发现先写出显式形式有助于后续使用高阶函数）。
3. 应用这些启发式方法对输入如何处理做出假设。提示：几乎从未想要使用foldl。
4. 使用GHCi：通过类型、预期结果和给REPL喂入一些示例输入来快速验证或反驳你的假设。

演练：使用GHCi实践

以...