Использование 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

foldr определяет семейство уравнений,

foldr g n [] = n
foldr g n [x] = g x (foldr g n []) = <b>g</b> x n
foldr g n [x,y] = g x (foldr g n [y]) = <b>g</b> x (<b>g</b> y n)
foldr g n [x,y,z] = g x (foldr g n [y,z]) = <b>g</b> x (<b>g</b> y (<b>g</b> z n))
                        ----- r ---------

и так далее.g - это функция редуктор ,

                    g x r = ....

, принимающая как x элемент списка ввода, и как r r результат r эвристическая обработка r est списка ввода (как видно из уравнений).

map, с другой стороны, определяет семействоуравнений

map f [] = []
map f [x] = [f x] = (:) (f x) [] = <b>((:) . f)</b> x []
map f [x,y] = [f x, f y] = <b>((:) . f)</b> x (<b>((:) . f)</b> y [])
map f [x,y,z] = [f x, f y, f z] = <b>((:) . f)</b> x (<b>((:) . f)</b> y (<b>((:) . f)</b> 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<sub>(<>,n)</sub> [] = n
fold<sub>(<>,n)</sub> (<b>xs</b> ++ <b>ys</b>) = fold<sub>(<>,n)</sub> <b>xs</b> <> fold<sub>(<>,n)</sub> <b>ys</b>

, а 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.

Вы также попросили некоторыессылки: см. например это , это и это .

Answer 2

Во-первых, давайте не будем использовать имя 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]

... и повторите для рекурсии.