Написание foldl с использованием foldr

В Real World Haskell , Глава 4 . on Функциональное программирование :

Напишите foldl с помощью foldr:

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Приведенный выше код меня сильно запутал, и кто-то по имени dps переписал его с понятным именем, чтобы сделать немного яснее:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

Кто-то другой, Jef G, затем отлично поработал, предоставив пример и шаг за шагом показывая базовый механизм:

myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3

Но я все еще не могу полностью понять это, вот мои вопросы:

  1. Что функция id для? Какая роль? Зачем он нам здесь?
  2. В приведенном выше примере функция id является аккумулятором в лямбда-функции?
  3. Прототип foldr - foldr :: (a -> b -> b) -> b - > [a] -> b , и первый параметр - это функция, которой требуются два параметра, но пошаговая функция в реализации myFoldl использует 3 параметра, я совершенно запутался!

73
задан halfer 29 July 2019 в 19:40
поделиться