库尔迪你帮我了解哈斯克尔中折叠器的实现类型?

Question

在标题为"Programming in Haskell"的书中，第77页，有一个foldr的实现，以解释函数。它看起来像这样：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

为什么类型不是这样：

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

第一个参数是一个函数 (a -> b -> b)，将始终应用于列表的头部和递归处理的尾部。

但是，什么是一个例子，其中头部和递归处理的尾部最终具有不同的类型？

我当然不明白这里的事情。您能否分解为折叠器实现编写类型的过程？

Answer 1

请注意，在函数传递的每个点上，传递的尾部都是递归调用foldr的结果。由于foldr返回类型b，函数类型为a -> b -> b是有意义的：它的第一个参数是head，第二个参数是递归foldr调用的结果。

此外，基本情况是b类型，因为foldr调用[]只是返回基本情况。

---

手动扩展foldr对具体示例的评估内容(来自威廉对该问题的评论)可能会有所帮助。

例如

foldr (:) [] [1,2,3]
= (:) 1 (foldr (:) [] [2,3])
= (:) 1 ((:) 2 (foldr (:) [] [3]))
= (:) 1 ((:) 2 ((:) 3 (foldr (:) [] [])))
= (:) 1 ((:) 2 ((:) 3 [])) -- base case used here
= (:) 1 ((:) 2 [3])
= (:) 1 [2,3]
= [1,2,3]

在这里，应用于头部和尾部的函数是Int -> [Int] -> [Int]型，意思是a = Int和b = [Int]。

旁注：确实foldr (:) [] = id

.

Answer 2

您可以将b视为计算状态，而a视为输入数据。您向后遍历列表并对顺序输入(类型a)做出反应。要描述此计算，您需要 3 件事：

• 一种更新新输入(a)上的状态(类型b)的方法。因此，您需要一个函数来接受输入，先前状态并生成新状态：a -> b -> b
• 一些初始状态(ofc，b)
• 输入/事件的序列 – 在本例中为a的列表。

以显示每种类型用途的方式重写foldr类型可能更清楚：

foldr :: (input -> state -> state) -> state -> [input] -> state
foldr update initialState inputs = case inputs of
[]  -- no inputs, so we leave it as it was
-> initialState
(input : rest) ->
let -- update state on all of the other inputs
prevState = foldr update initialState rest
-- update state on the current input
newState = update input prevState
in newState

在foldl上更容易看到这种流动。那么在foldr中，遍历的顺序只是颠倒了。