В 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
Но я все еще не могу полностью понять это, вот мои вопросы:
foldr :: (a -> b -> b) -> b - > [a] -> b
, и первый параметр - это функция, которой требуются два параметра, но пошаговая функция в реализации myFoldl использует 3 параметра, я совершенно запутался!