Определение сгибания в терминах сгибания

Question

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)

В настоящее время я читаю книгу о Haskell. И в нем он написал свою собственную версию функции foldl, но в терминах foldr. Я не понимаю.

1. Почему есть 4 аргумента для фолдера?
2. Что делает функция id?

Answer 1

Дело станет очевидным, когда расширить выражение foldr step id xs z:

Как сказал Адам Смит в комментариях:

идентификатор шага сворачивания xs z = (идентификатор шага сворачивания xs) z

Рассматривать foldr step id xs во-первых

foldr step id xs
= x1 `step` (foldr step id xs1)
= x1 `step` (x2 `step` (foldr step id xs2))
...
= x1 `step` (x2 `step` ... (xn `step` (foldr step id []))...)
= x1 `step` (x2 `step` ... (xn `step` id)...)

где

xs = (x1:xs1)
xs1 = (x2:xs2), xs = (x1:x2:xs2) 
....
xsn = (xn:[]), xs = (x1:x2...xsn) respectively 

Теперь примените вышеуказанную функцию с аргументом z, т.е.

(x1 `step` (x2 `step` ... (xn `step` id)...)) z

и разреши

g = (x2 `step` ... (xn `step` id)...) 

дает

(x1 `step` g) z

т.е.

(step x1 g) z

и теперь примените часть where к foldl:

где шаг x g a = г (факс)

дает

(step x1 g) z = step x1 g z = g (step z x1)

где

g (step z x1) = (x2 `step` (x3 step ... (xn `step` id)...) (step z x1)

позволять

g' = (x3 step ... (xn `step` id)...)

дает

(x2 `step` g') (step z x1)
= step x2 g' (step z x1)
= g' (step (step z x1) x2))
= (x3 step ... (xn `step` id)...) (step (step z x1) x2))

повторяет те же шаги, наконец, у нас есть,

(xn `step` id) (step ....(step (step z x1) x2)....)
= step xn id (step ....(step (step z x1) x2)....)
= id (step (step ....(step (step z x1) x2)....) xn)
= (step (step ....(step (step z x1) x2)....) xn)
= foldl step z xs

и теперь очевидно, что зачем использовать функцию id. наконец, понять почему

foldl step z xs = (step (step ....(step (step z x1) x2)....) xn)

начальный случай:

foldl step z' [] = z'

рекурсивный случай:

foldl step z (x1:xs1) 
= foldl step (step z x1) xs1
= foldl step (step (step z x1) x2) xs2
...
= foldl step (step (step ....(step (step z x1) x2)....) xn) []
= (step (step ....(step (step z x1) x2)....) xn)

где

z' = (step (step ....(step (step z x1) x2)....) xn) in initial case

Так же, как и выше.

Answer 2

Как говорит Adam Smith в комментариях, есть только три аргумента foldr, Рассматриваемая строка анализируется следующим образом:

myFoldl f z xs = (foldr step id xs) z

Конечно, есть и другие неявные скобки, но это важные.

Вот переписать с аннотациями типа, предполагая переменные типа области действия (то есть a а также b означают одни и те же типы во всем этом определении).

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs =  goFold z
   where
      goFold :: a -> a
      goFold = foldr step id xs
      step :: b -> (a -> a) -> (a -> a)  -- Last brackets are redundant
      step x g a = g (f a x)

Я переместил foldr вызов в отдельное значение goFold так что вы можете увидеть его тип и как он применяется к z значение. step функция накапливает b значения в функцию типа (a -> a), каждый b значение обработано goFold добавляет еще один из них. "Ноль" для функций, конечно, id из прелюдии:

id :: a -> a
id x = x

-> оператор функции в типах является ассоциативным справа, поэтому последняя пара скобок в step типа избыточны. Но я написал это так, потому что это подчеркивает, каким образом step используется; он принимает значение и функцию и возвращает новую функцию.