我理解简单的 foldr 语句,例如
foldr (+) 0 [1,2,3]
但是,我在处理更复杂的 foldr 语句时遇到了麻烦,即在函数中采用 2 个参数以及使用 / 和 - 计算的语句。谁能解释为获得这些答案而发生的步骤?
foldr (\x y -> (x+y)*2) 2 [1,3] = 22
foldr (/) 2 [8,12,24,4] = 8.0
谢谢。
我理解简单的 foldr 语句,例如
foldr (+) 0 [1,2,3]
但是,我在处理更复杂的 foldr 语句时遇到了麻烦,即在函数中采用 2 个参数以及使用 / 和 - 计算的语句。谁能解释为获得这些答案而发生的步骤?
foldr (\x y -> (x+y)*2) 2 [1,3] = 22
foldr (/) 2 [8,12,24,4] = 8.0
谢谢。
折叠的函数参数总是有两个参数。(+)
并且(/)
是二进制函数,就像第二个示例中的函数一样。
Prelude> :t (+)
(+) :: Num a => a -> a -> a
如果我们将第二个示例改写为
foldr f 2 [1,3]
where
f x y = (x+y)*2
我们可以使用与我们使用的完全相同的方案来展开正确的折叠(+)
:
foldr f 2 [1,3]
foldr f 2 (1 : 3 : [])
1 `f` foldr f 2 (3 : [])
1 `f` (3 `f` foldr f 2 [])
1 `f` (3 `f` 2)
1 `f` 10
22
值得注意的是它foldr
是右结合的,它显示了括号是如何嵌套的。相反,foldl
及其有用的表亲foldl'
是左结合的。
foldr
函数定义如下:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ a [] = a
foldr f a (x:xs) = f x (foldr f a xs)
现在考虑以下表达式:
foldr (\x y -> (x + y) * 2) 2 [1,3]
我们将给 lambda 起一个名字:
f x y = (x + y) * 2
因此:
foldr f 2 [1,3]
-- is
f 1 (foldr f 2 [3])
-- is
f 1 (f 3 (foldr f 2 []))
-- is
f 1 (f 3 2)
-- is
f 1 10
-- is
22
相似地:
foldr (/) 2 [8,12,24,4]
-- is
8 / (foldr (/) 2 [12,24,4])
-- is
8 / (12 / (foldr (/) 2 [24,4]))
-- is
8 / (12 / (24 / (foldr (/) 2 [4])))
-- is
8 / (12 / (24 / (4 / (foldr (/) 2 []))))
-- is
8 / (12 / (24 / (4 / 2)))
-- is
8 / (12 / (24 / 2.0))
-- is
8 / (12 / 12.0)
-- is
8 / 1.0
-- is
8.0
希望有帮助。
您可以将foldr
、maybe
和either
视为将其各自类型的数据构造函数替换为您选择的函数和/或值的函数:
data Maybe a = Nothing | Just a
maybe :: b -> (a -> b) -> Maybe a -> b
maybe nothing _just Nothing = nothing
maybe _nothing just (Just a) = just a
data Either a b = Left a | Right b
either :: (a -> c) -> (b -> c) -> Either a b -> c
either left _right (Left a) = left a
either _left right (Right b) = right b
data List a = Cons a (List a) | Empty
foldr :: (a -> b -> b) -> b -> List a -> b
foldr cons empty = loop
where loop (Cons a as) = cons a (loop as)
loop Empty = empty
所以一般来说,你不必考虑所涉及的递归,只需将其视为替换数据构造函数即可:
foldr f nil (1 : (2 : (3 : []))) == (1 `f` (2 `f` (3 `f` nil)))