Объяснение функций карты (с использованием foldr) в Haskell?

Question

Я пытаюсь определить функцию карты, используя foldr

Я нашел два следующих решения, однако я не совсем уверен, как они работают.

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

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

Я новичок в Haskell и foldr, поэтому я пытаюсь понять, что делает ((:) . f) в первом решении и что (\x xs -> f x : xs) во втором решении.

Я также не понимаю, как foldr может обрабатывать случай пустого списка.

Было бы очень полезно, если бы я мог получить простое пошаговое объяснение этого, с точки зрения непрофессионала.

Answer 1

И (\x xs -> f x : xs), и (:) . f означают одно и то же. Они обе функции, которые принимают два аргумента, применяют f к первому аргументу, а затем заключают его во второй аргумент.

Так что же делает foldr при получении пустого списка? Он просто возвращает начальное значение, которое в этих примерах равно [].

Вот реализация foldr из Hackage :

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys