使用foldr定义地图(开发)

Question

很难理解折叠...扩展是否正确？也会欣赏任何会使折叠更容易消化的链接或类比.

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

Answer 1

首先,我们不要使用这个名称,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])

现在我们可以进行β减少:

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

...并重复递归.

Answer 2

foldr 定义了一族方程,

foldr g n [] = n
foldr g n [x] = g x (foldr g n []) = g x n
foldr g n [x,y] = g x (foldr g n [y]) = g x (g y n)
foldr g n [x,y,z] = g x (foldr g n [y,z]) = g x (g y (g z n))
                        ----- r ---------

等等.g是减速器功能,

                    g x r = ....

接受作为x输入列表的元素,并且作为r所述ř的esult ř ecursively处理ř输入列表的EST(如可在方程式中可以看出).

map另一方面,定义了一族方程

map f [] = []
map f [x] = [f x] = (:) (f x) [] = ((:) . f) x []
map f [x,y] = [f x, f y] = ((:) . f) x (((:) . f) y [])
map f [x,y,z] = [f x, f y, f z] = ((:) . f) x (((:) . f) y (((:) . f) z []))
                                =  (:)  (f x) ( (:)  (f y) ( (:)  (f z) []))

两个家庭完全匹配

g = ((:) . f) = (\x -> (:) (f x)) = (\x r -> f x : r)

而且n = [],因此

foldr ((:) . f) [] xs  ==  map f xs

我们可以通过输入列表长度上的数学归纳来严格证明这一点,遵循定义的定律foldr,

foldr g n [] = []
foldr g n (x:xs) = g x (foldr g n xs)

这是本文顶部方程式的基础.

现代Haskell有Fodable类型类,其基本fold遵循法则

fold(<>,n) [] = n
fold(<>,n) (xs ++ ys) = fold(<>,n) xs <> fold(<>,n) ys

并且map在其术语中自然定义为

map f xs  =  foldMap (\x -> [f x]) xs

转[x, y, z, ...]进[f x] ++ [f y] ++ [f z] ++ ...,由于名单(<>) == (++).这来自等价

    f x : ys  ==  [f x] ++ ys

这也让我们可以filter轻松地定义相同的线条

filter p xs  =  foldMap (\x -> [x | p x]) xs

对于您的具体问题,扩展是正确的,除了 (*2 x)应该写为((*2) x),与之相同(x * 2).(* 2 x)不是有效的Haskell(虽然有效的Lisp :)).

类似(*2)的函数被称为" 运算符部分 " - 缺少的参数进入空槽:(* 2) 3 = (3 * 2) = (3 *) 2 = (*) 3 2.

您还要求提供一些链接:请参阅例如this,this和this.