使用文件夹定义地图(开发) [英] Using foldr to define map (develop)

问题描述

很难理解折叠...扩展正确吗?也请您欣赏任何能使折页更易理解的链接或类比.

Having a hard time understanding fold... Is the expansion correct ? Also would appreciate any links, or analogies that would make fold more digestible.

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 : []))

推荐答案

首先，我们不要使用名称 foldMap ，因为该名称已经

First, let's not use the name foldMap since that's already a standard function different from map. If you want to re-implement an existing function with the same or similar semantics, convention is to give it the same name but either in a separate module, or with a prime ' appended to the name. Also, we can omit the empty-list case, since you can just pass that to the fold just as well:

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

现在，如果您想手动评估此功能，请先使用该定义，而无需再插入其他任何内容:

Now if you want to evaluate this function by hand, first just use the definition without inserting anything more:

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]

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

Now to evaluate this through, you also need the definition of foldr. It's actually a bit different in GHC, but effectively

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])

现在我们可以进行β还原:

Now we can perform a β-reduction:

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

...然后重复递归.

...and repeat for the recursion.

这篇关于使用文件夹定义地图(开发)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！