具有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]位是我们正在压缩,折叠,减少的列表.

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的定义,带有一些暗示变量名

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