首页 文章

使用foldl foldr定义函数

提问于
浏览 次
1

我理解foldl，foldr的定义，但我对它们定义的函数有问题 .

例如，带有foldr的 Map ：

map f []       = []
map f l   = foldr (\x xs -> f x : xs) [] l

我不明白 (\x xs -> f x : xs) . 它是map函数，foldr采用哪种？但不应该是 (\x xs -> f x : f xs) ，因为 map f (x:xs) = f x : map f xs ？

foldl的示例：

concat (x:xs) = x ++ concat xs

concat' xs = foldl (++) [] xs
concat'' xs = foldl (\ys y -> ys ++ y) [] xs

当然我理解 (++) ，但 (\ys y -> ys ++ y) 背后的逻辑是什么？是 ys = [] 和 y = xs ？所以该函数将 [] 视为 ys 而 y 是 xs 的第一个元素，并将 [] 与 y 连接？具体例子：

concat'' [1,2,3] = foldl (\ys y -> ys ++ y) [] [1,2,3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [] [1]) [2,3]
=> foldl (\ys y -> ys ++ y) [1] [2,3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1] [2]) [3]
=> foldl (\ys y -> ys ++ y) [1,2] [3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1,2] [3]) []
=> foldl (\ys y -> ys ++ y) [1,2,3] []
=> [1,2,3]

另一件事： concat 只需要1个列表 xs ，所以如果我要连续2个列表？

concat (x:xs) ys = x ++ concat xs ys
concat [1,2,3] [4,5,6] with foldl?

相反：

reverse (x:xs) = reverse xs ++ [x]

reverse'  l = foldl (\xs x -> [x] : xs) [] l
reverse'' l = foldr (\x xs -> xs ++ [x]) [] l

折叠器直观清晰（带有上面的问题），但是在foldl (\xs x -> [x] : xs) 中反向顺序的背后是什么？这个 foldl (\x xs -> xs ++ [x]) [] l 会错的，不是吗？

非常感谢！

haskell dictionary functional-programming fold

1 回答

  • 2

    代码

    foldr (\x xs -> ...) end list

    可以粗略地阅读如下

    • 扫描整个 list

    • 如果它是空的，只需返回 end

    • 否则：

    • 让 x 成为手边的元素

    • 让 xs 成为处理后的列表的其余部分

    • 应用 ... 操作

    强调的部分至关重要 . xs 不是列表的其余部分，而是"recursive call"的结果 .

    事实上， xs 是一个坏名字 . 在一般情况下，它甚至不是一个列表！例如 . 一个人永远不会写（愚蠢的例子）

    foldr (\x xs -> x + xs) 0 [1..100]  -- sum 1..100

    但更喜欢像

    foldr (\x partialSum -> x + partialSum) 0 [1..100]  -- sum 1..100

    （实际上，人们不会使用 foldr 求和，但让我们把它放在一边 . ）

    所以，就像这样读：

    map f l   = foldr (\x mappedTail -> f x : mappedTail) [] l
    回复于

相关问题