Используйте foldr для определения карты в Haskell,

Question

Я новичок в Haskell и постараюсь понять map Функция.

Я понимаю следующее до сих пор.

map::(a->b)->[a]->[b] 
map f (x:xs) = f x : map f xs 

Но я не понимаю следующее определение: Использование foldr определить Map

map'::(a->b)->[a]->[b] 
map' f = foldr ((:).f) [] 

Может кто-нибудь объяснить выше карту»определение и почему так же, как карта

Answer 1

Давайте посмотрим на the source of foldr:

foldr k z = go where 
    go []  = z 
    go (x:xs) = k x (go xs) 

Теперь давайте сравним определение map к определению go выше:

map f []  = [] 
map f (x:xs) = f x : map f xs 

Он выглядит очень похожим лар, не так ли? Давайте перепишем второе предложение, чтобы вытащить часть, которая сочетает в себе x с результатом рекурсивного вызова в:

map f []  = [] 
map f (x:xs) = (\v vs -> f v : vs) x (map f xs) 

Теперь параллельно очень ясно; мы можем даже написать несколько имен, чтобы кристаллизовать параллель:

map f []  = z    where z = [] 
map f (x:xs) = k x (map f xs) where k = \v vs -> f v : vs 

Просто заменить go везде вы видите map f в выше, и вы увидите, что эти определения идентичны! Таким образом, в духе DRY, мы можем попытаться повторно foldr для выше:

map f = foldr (\v vs -> f v : vs) [] 

Это получает вам большую идею о том, как получить от map до foldr. Получение полного пути к определению, которое вы дали, - это просто некоторые синтаксические трюки. Мы будем говорить о функции аргумента foldr Сейчас:

\v vs -> f v : vs 
= { writing the infix operator prefix instead } 
\v vs -> (:) (f v) vs 
= { eta reduction } 
\v -> (:) (f v) 
= { definition of function composition } 
\v -> ((:) . f) v 
= { eta reduction } 
(:) . f 

Таким образом, используя эту цепочку рассуждений, мы можем достичь окончательной формы

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

Answer 2

Для начала вам необходимо знать

foldr (:) [] 

другой только применяя функцию f прежде, чем минусов, поэтому эквивалентно карте

Answer 3

альтернативный ответ, мы надеемся, более доступным для некоторых людей.

foldr f z xs заменяет каждый : в xs с f и [] с z.Так

a : b : c : d : [] 

становится

a `f` b `f` c `f` d `f` z 

Теперь давайте заменяющие значения из определения map'.

a `(:).f` b `(:).f` c `(:).f` d `(:).f` [] 

(Я немного растягиваю синтаксис Haskell).

Теперь

a `(:).f` as 

такого же, как

(:) (f a) as 

, который так же, как

f a : as 

Продолжая остроумие этого преобразования, мы получаем

f a : f b : f c : f d : [] 

Эй, это похоже на прямую map f применительно к [a,b,c,d], не так ли?