list - 将 foldl 写为 foldr 混淆

Question

我知道还有其他关于此的帖子，但我的略有不同。

我有一个执行 foldl 任务的函数, 使用 foldr .我有给我的解决方案，但需要帮助理解。
foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

它被称为使用这样的东西:
foldlTest (-) [1,2,3] 10 = -4
我理解的第一件事是我的函数接受 2 个参数，但在上面的测试用例中给出了 3 个。这意味着 10将参与我假设的 lambda 表达式。

1) 是否10代替b在 b -> b ? (那么 b 将是初始累加器值)

我不明白的是(\x r b -> r (f b x))部分是。

2) 每个变量的值是多少？我对这个 lambda 函数感到非常困惑。

3) lambda 函数究竟做了什么，它与常规 foldr 有何不同？ ?

Answer 1

好吧，由于我们的 Haskell 常驻专家还没有站出来解释这一点，我想我可以试一试。请大家随意纠正您认为错误的任何内容，因为我真的只是在摸索这里的答案，而以下内容本质上会有点漫无边际。

首先，像在 Haskell 中一样，查看类型是个好主意:

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

因为我们只对这里的列表感兴趣，而不是通用 Foldable s，让我们专门用于:

foldl ::  (b -> a -> b) -> b -> [a] -> b

并与您获得的功能进行比较:

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

由于 Haskell 函数是柯里化的，这是 -> 的另一种说法。类型签名中的箭头是右结合的，最后一对括号是不必要的，所以这与:

foldlTest:: (b -> a -> b) -> [a] -> b -> b

与 foldl 的比较在上面，我们看到它们是相同的，除了最后两个参数 - [a]和 b ——被翻过。

所以我们已经可以观察到，而库函数foldl接受一个折叠函数、一个起始累加器和一个要折叠的列表，以产生一个新的累加器 foldlTest version 接受一个折叠函数、一个要折叠的列表和一个起始累加器，以产生一个新的累加器。这听起来完全一样，但如果我们现在重新引入我在几步前取下的那对括号，我们会看到 foldlTest ，在你所展示的形式中，可以被认为是:

取一个折叠函数和一个列表，并产生一个函数 b -> b它描述了折叠列表如何将初始累加器转换为最终结果。

特别注意，在这个公式中，它返回的确实是一个函数。

所以现在我们准备好查看您所看到的实际实现:

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

我会第一个承认这相当复杂，甚至令人困惑。一如既往，让我们检查一下类型。

输入类型很简单。从上面的讨论中我们知道f有类型 b -> a -> b , 和 xs有类型 [a] .

好的，那个 lambda 怎么样？让我们分阶段来看:

它需要 3 个参数，x , r和 b ， 以该顺序。

函数调用的结果是r (f b x) .如果我们坐下来考虑一下，这已经告诉了我们很多!

一方面，我们知道 f有类型 b -> a -> b ，所以来自 f b x我们知道 b有类型 b和 x有类型 a .

至于r ，我们看到它一定是一个函数，因为它应用于f b x .我们知道后者的类型为 b (来自 f 的类型签名)。所以r有类型 b -> c , 对于某些类型 c .

因此，我们复杂的 lambda 函数具有类型 a -> (b -> c) -> b -> c ，其中 c是我们尚未确定的某种类型。

现在到了一个关键点。这个 lambda 作为第一个参数(折叠函数)提供给 foldr功能。因此它必须具有类型 d -> e -> e , 对于某些类型 d和 e .

请记住，函数是柯里化的，尽管 lambda 的签名看起来有 3 个参数，但我们可以通过重写为 a -> (b -> c) -> (b -> c) 将其减少到 2 个。 .这与我们知道的签名完全匹配 foldr正在寻找，与d等于 a和 e等于 b -> c .

我们专业 foldr的签名使其接受这种类型的函数，我们发现它是:

foldr :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)`

我们仍然不知道是什么c是 - 但我们不必再怀疑了。上面是一个折叠的签名，它覆盖了 a 的列表。 s，并从 b 产生一个函数至 c . foldr 的下一个参数, 类型为 b -> c , 给出(由我们试图破译的实现)为 \b -> b .当然，这只是恒等函数，关键是它是从类型到自身的函数。所以b -> c类型实际上必须是 b -> b ，或者换句话说 c与 b 相同一直!

因此 lambda 必须具有以下类型:

a -> (b -> b) -> (b -> b)

它需要一个 a ，以及 b 上的自同态(这只是意味着从 b 到自身的函数)，并返回 b 上的另一个自同态.这就是我们将折叠 a 列表的函数s with，以恒等函数为起点，产生自同态b -> b这将实现我们所追求的左折叠。

鉴于 a，上面的类型签名本身并没有给我们太多关于如何实现它的线索。和 b可以是任何东西。但是，我们确实有我们的函数 f将它们联系起来 - 回想一下，它需要一个 b和一个 a ，并产生 b .鉴于(通过再次撤消柯里化)，上述函数需要我们，给定 a , b -> b函数和 b , 产生另一个 b ，我只能看到两种非平凡的方法:

将该函数应用于 b ，然后申请 f到 a和结果。

申请 f到 a和 b ，然后应用 b -> b函数到结果

这两个中的第二个正是您要问的那个 lambda 的作用，希望现在可以通过查看它而变得明显。 (第一个选项应该写成 \x r b -> f (r b) x 。我实际上不确定这会产生什么整体效果，尽管我没有考虑太多。)

我已经涵盖了很多领域，尽管感觉比实际情况要多，因为我已经尝试非常艰苦。回顾一下，什么是 foldlTest函数确实是，给定一个列表 a s 和一个函数 f :: b -> a -> b , 产生一个函数 b -> b它是通过从恒等函数开始构建的，沿着列表从右到左移动，改变当前函数 r :: b -> b到发送 b 的那个至 r (f b x) - 哪里x :: a是我们当前所在的列表的元素。

这是对 foldlTest 内容的一种相当算法化的描述做。让我们试着看看它对一个实际的列表做了什么——不是一个具体的列表，而是一个 3 元素列表 [a1, a2, a3] .我们从恒等函数开始 \b -> b ，并依次将其转化为:

b -> f b a3 (回想一下 r 作为恒等函数开始)

b -> f (f b a2) a3 (这只是将之前的函数 r 代入 \b -> r (f b x) ， a2 现在扮演 x 的角色)

b -> f (f (f b a1) a2) a3

我希望你现在可以看到这看起来很像用相同的函数从左边折叠列表 f . “看起来非常像”，我的意思实际上是相同的! (如果你以前没有见过或尝试过，试着写出 foldl f b [a1, a2, a3] 的连续阶段，你会看到相同的模式。)

再次道歉，这有点乱，但我希望这已经为您提供了足够的信息来回答您提出的问题。如果它让您的大脑受到一点伤害，请不要担心 - 我的也一样! :)