时间戳

首页 > 解决方案 > 使用 foldr 定义地图（开发）

haskell - 使用 foldr 定义地图（开发）

问题描述

很难理解 fold... 展开是否正确？也将不胜感激任何可以使折叠更易于消化的链接或类比。

foldMap :: (a -> b) -> [a] -> [b]
foldMap f [] = []
foldMap f xs = foldr (\x ys -> (f x) : ys) [] xs


b =  (\x ys -> (f x):ys)
foldMap (*2) [1,2,3]
= b 1 (b 2 (foldr b [] 3))
= b 1 (b 2 (b 3 ( b [] [])))
= b 1 (b 2 ((*2 3) : []))
= b 1 ((*2 2) : (6 :[]))
= (* 2 1) : (4 : (6 : []))
= 2 : (4 : (6 : []))

标签： haskellfoldcurrying

解决方案

首先，我们不要使用名称foldMap，因为这已经是不同于map. 如果您想重新实现具有相同或相似语义的现有函数，约定是给它相同的名称，但可以在单独的模块中，或者'在名称后附加一个撇号。此外，我们可以省略空列表的情况，因为您也可以将其传递给折叠：

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x ys -> f x : ys) [] xs

现在如果你想手动评估这个函数，首先只使用定义而不插入任何东西：

map' (*2) [1,2,3,4]
 ≡ let f = (*2)
       xs = [1,2,3,4]
   in foldr (\x ys -> (f x) : ys) [] xs
 ≡ foldr (\x ys -> (*2) x : ys) [] [1,2,3,4]

现在稍微美化一下：

 ≡ foldr (\x ys -> x*2 : ys) [] [1,2,3,4]

现在要对此进行评估，您还需要foldr. 它实际上在 GHC 中有点不同，但有效

foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

所以用你的例子

  ...
 ≡ foldr (\x ys -> x*2 : ys) [] (1:[2,3,4])
 ≡ (\x ys -> x*2 : ys) 1 (foldr (\x ys -> x*2 : ys) [] [2,3,4])

现在我们可以执行 β-reduction：

 ≡ 1*2 : foldr (\x ys -> x*2 : ys) [] [2,3,4]
 ≡ 2 : foldr (\x ys -> x*2 : ys) [] [2,3,4]

...并重复递归。

推荐阅读