具有折叠器和折叠的高阶函数细节

Question

我在解释折叠的函数签名时遇到问题。我了解它是如何工作的，但我不确定它与签名有何关系。

我对它的细节有几个问题

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (+) 5 [1,2,3,4]

似乎第一个参数需要一个加法函数：

(a -> b -> b)

在函数参数中，究竟发生了什么？本部分是否将最右侧的整数a应用于累加器b以在这种情况下产生另一个整数 9？在此之后，它是否返回一个将累加器作为参数的函数？

在此之后，下面的最后两个参数是什么意思？

[a] -> b

非常感谢。

Answer 1

当你将(+)传递给foldr的第一个参数时，你隐式声明a与b相同。这很令人困惑，因为我们倾向于重用名称，但是如果我为类型变量使用相同的命名空间将它们一起编写

(+)       :: Num i => i -> i -> i
foldr     :: (a -> b -> b) -> b -> [a] -> b
foldr (+) :: Num i => i -> [i] -> i

其中第三行暗示i ~ a和i ~ b因此，通过传递性，a ~ b .此外，这里可能更清楚地看到，foldr (+)中剩余的第一个参数是折叠的"初始"值，[i]位是我们正在压缩、折叠、减少的列表。

用更

常见的名字来称呼foldr (+) 0可能更清楚，sum :: Num a => [a] -> a 。我们也有foldr (*) 1 product :: Num a => a -> [a].

所以是的，您对累加器函数在foldr (+)中的行为方式的描述是完全正确的，但比一般函数更具体。例如，我们可以使用foldr来构建一个 Map .

foldr ((k, v) m -> Map.insert m k v) Map.empty :: Ord k => [(k, v)] -> Map k v

在这种情况下，累加

器函数获取我们的关联列表，并不断将值插入到我们的累加*ing* Map中，该 从空开始。为了在这里彻底理解，让我再次写出所有类型

((k, v) -> m -> Map.insert m k v)       :: Ord k => (k, v) -> Map k v -> Map k v
foldr                                    :: (a -> b -> b) -> b -> [a] -> b
foldr ((k, v) -> m -> Map.insert m k v) :: Ord k => Map k v -> [(k, v)] -> Map k v

我们强迫a ~ (k, v)和b ~ Map k v的地方.

---

作为对此事的最终看法，这里是折叠器的定义，其中包含一些暗示性的变量名称

foldr _    b []     = b
foldr (<>) b (a:as) = a <> foldr f b as

因此，您可以看到(<>) :: a -> b -> b如何结合a和b类型。我们可以显式地"运行"这个定义，看看它是如何建立计算的。

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

当我们使用非对称操作（如上面Map示例）时，这可能会更加清楚。下面我使用 {{ k -> v, k -> v }} 来表示Map，因为它不能直接打印。

-- inserts a single (k,v) pair into a Map
ins :: Ord k => (k, v) -> Map k v -> Map k v
ins (k, v) m = Map.insert m k v
foldr ins Map.empty [('a', 1), ('b', 2)]
ins ('a', 1) (foldr ins Map.empty [('b', 2)])
ins ('a', 1) (ins ('b', 2) (foldr ins Map.empty []))
ins ('a', 1) (ins ('b', 2) Map.empty)
ins ('a', 1) (ins ('b', 2) {{  }})
ins ('a', 1) {{ 'b' -> 2 }}
{{ 'b' -> 2, 'a' -> 1 }}

Answer 2

这取决于你如何看待它。第一步产生(+) 1 (foldr (+) 5 [2,3,4])。当您尝试使用折叠结果时，这将强制计算 （+） 的第二个参数，并且由于 （+） 是严格的，这将解开整个列表。最后一步产生(+) 1 ((+) 2 ((+) 3 ((+) 4 5)))。所以，是的，添加的前两个数字是 4 和 5，但这不是 foldr 做的第一件事，在这种情况下，您将首先将列表替换为一棵 thunks 树，然后对其进行评估以获得所有数字和 5 的总和。

在函数不严格的情况下，用 thunks 替换列表是很好的 - 这样你就可以只评估必要的数量，甚至是可能是无限的列表。在函数严格的情况下，考虑使用 foldl' 重写是有意义的。

Answer 3

这是折叠器的类型签名：

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

它需要一个函数（称为step），该函数获取下一个值（a）和累积值（a b）并产生一个新的累积值（也是b）

step :: a -> b -> b

和一个初始累加器值 （a b）：

initialValue :: b

以及要折叠的输入列表（a的列表）：

inputs :: [a]

最后你得到一个输出（a b）

output :: b

所以你得到一个一般的形式：

output = foldr step initialValue inputs