haskell - 折叠 foldr 函数组合 - Haskell

Question

所以，我真的在努力理解 foldl.foldr 的组成。这是一个例子：

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]

结果是 22，但这里到底发生了什么？

在我看来，这就是正在发生的事情：foldl (+) 1 [6,15]. 我的怀疑与该foldr部分有关。它不应该将 1 添加到所有子列表中吗？像这样：foldr (+) 1 [1,2,3]。在我的脑海中，1 只添加了一次，对吗？（可能不是，但我想知道如何/为什么！）。

我很困惑（也许让所有的困惑，哈哈）。谢谢！

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]

变成

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]]

所以你得到

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]]

在 的第一步之后foldl，或

foldl (foldr (+)) 7 [[4,5,6]]

如果我们评估应用foldr程序（除非严格分析器启动，它实际上仍然是一个未评估的 thunk，直到foldl遍历整个列表，但下一个表达式在评估后更具可读性），这就变成了

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) []

最后

foldl (foldr (+)) 22 []
~> 22

Answer 2

让我们检查一下foldl . foldr。他们的类型是

foldl :: (a -> b -> a) -> (a -> [b] -> a)
foldr :: (c -> d -> d) -> (d -> [c] -> d)

我故意使用了不同的类型变量并添加了括号，以便我们现在将它们视为一个参数的函数（并且它们的结果是函数）变得更加明显。看着foldl我们看到它是一种提升函数：给定一个a从ausing产生的函数b，我们提升它以便它继续工作[b]（通过重复计算）。功能foldr类似，只是参数颠倒了。

现在如果我们申请会发生什么foldl . foldr？首先，让我们推导类型：我们必须统一类型变量，以便 的结果foldr与 的参数匹配foldl。所以我们必须替换: a = d, b = [c]:

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d)
foldr :: (c -> d   -> d) -> (d -> [c] -> d)

所以我们得到

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d)

它的含义是什么？首先，foldr提升类型的参数c -> d -> d以在列表上工作，并反转它的参数，以便我们得到d -> [c] -> d. 接下来，foldl再次解除此功能以处理[[c]]- 列表[c]。

在您的情况下，被解除的操作(+)是关联的，因此我们不关心其应​​用程序的顺序。双重提升只是创建了一个将操作应用于所有嵌套元素的函数。

如果我们使用 just foldl，效果会更好：我们可以多次提升，例如

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

Answer 3

其实，(foldl.foldr) f z xs === foldr f z (concat $ reverse xs)。

即使f是关联操作，正确的应用程序顺序也很重要，因为它会影响性能。

我们从

(foldl.foldr) f z xs
foldl (foldr f) z xs

写一会儿，这g = foldr f是[x1,x2,...,xn_1,xn] = xs

(...((z `g` x1) `g` x2) ... `g` xn)
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ... )
foldr f z $ concat [xn,xn_1, ..., x1]
foldr f z $ concat $ reverse xs

所以在你的情况下，正确的减少顺序是

(foldl.foldr) 1 [[1,2,3],[4,5,6]]
4+(5+(6+(  1+(2+(3+  1)))))
22

以机智，

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]]
[7,8,4,5,6,1,2,3]

---

同样，(foldl.foldl) f z xs == foldl f z $ concat xs。与snoc a b = a++[b],

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]]
[1,2,3,4,5,6,7,8]

还有(foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs)，等：

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[1,2,3,4,5,6,7,8]
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[7,8,1,2,3,4,5,6]
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]]
[7,8,4,5,6,1,2,3]