haskell - foldr 和 foldl 的高阶函数细节

Question

我无法解释 foldl 的函数签名。我了解它是如何工作的，但我不确定它与签名有何关系。

我有几个关于它的细节的问题

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] bit 是我们正在压缩、折叠、缩减的列表。

调用 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

在这种情况下，累加器函数获取我们的关联列表并不断将值插入到我们的 accumulat*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 的定义，带有一些暗示性的变量名称

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 }}