Функция foldl

Здесь очень важно остановиться и подумать, что и где мы делаем не так, где наша логика оторвалась от жизни. Вернемся к нашей функции zoo еще раз:

zoo [] acc = acc

zoo (x:xs) acc = zoo xs (x:acc)

Вот как она работает:

zoo [1,2,3] [] → zoo [2,3] [1] → zoo [3] [2,1] → zoo [] [3,2,1] → [3,2,1]

А теперь вспомним, что функция foldr как бы расставляет свою операцию между всеми элементами списка по схеме:

x₁ f (x₂ f (x₃ f … (x_N f z)

Ну-ка, подставим на место f операцию (:), а на место нулевого элемента – пустой список:

x₁ : (x₂ : (x₃ : … (x_N : [])

Теперь очевидно, почему ничего со списком не изменилось, не так ли? И одновременно это означает, что функция foldr не может реализовать нашу функцию zoo, по крайней мере, так легко, как мы на это надеялись.

А как тогда записать результат работы функции zoo, в виде списка элементов, между которыми расставлены какие-то операции?

([] : x₁) : x₂) : x₃) : … : x_N)…)

Постойте, операция (:) ведь требует, чтобы сначала ей дали элемент, а потом только список! Разумеется, вы правы, и нам придется переписать это выражение:

([] f x₁) f x₂) f x₃) f … f x_N)…),

где

f xs x = x:xs

Остановитесь и подумайте еще раз. Да, теперь у нас не правая свертка, а левая. И функция используется не обычная (:), а как бы перевернутая – это то же (:), но принимающее свои параметры в обратном порядке.

Кстати, это бывает нужно довольно часто, так что когда-то кому-то надоело плодить такие двойники функций, и он придумал функцию flip:

flip :: (a -> b -> c) -> b -> a -> c

flip f = \x y -> f y x

Так что, наша функция f – это всего лишь flip (:)

И при ближайшем рассмотрении-то, функция zoo ведет себя совсем не так, как foldr, это видно даже по тому, как используется нейтральный элемент, то бишь, начальное значение. Функция foldr проходит рекурсивно до конца списка, и соединяет с нейтральным элементом последнее значение.

А функция zoo с пустым списком соединяет первое значение списка. Ну еще бы они себя вели одинаково – это ведь разные свертки, левая и правая!

А что же функции hoo и doo? Они ведь были копией функции zoo? Давайте посмотрим, какую свертку реализуют они, левую или правую?

hoo [] acc = acc

hoo (x:xs) acc | x < acc = hoo xs x

| otherwise = hoo xs acc

doo [] acc = acc

doo (x:xs) acc | x > 0 = doo xs (acc+1)

| otherwise = doo xs acc

Они идут по списку, начиная с первого элемента до последнего, и начинают с того, что первый элемент как-то соединяют с аккумулятором. Да, это действительно левая свертка. Почему же у нас получился правильный результат, когда мы использовали foldr? Да потому что эти функции таковы, что у них получается одинаковый результат что слева, что справа! И действительно, какая разница, искать минимальный элемент, или подсчитывать количество положительных чисел, справа – или слева? Результат будет один!

Можно даже эти функции переписать так, что становится очевидным, почему foldr для них сработал нормально:

hoo [x] = x

hoo (x:xs) = min(x, hoo xs)

doo [] = 0

doo (x:xs) = (if x > 0 then 1 else 0) + doo xs

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

А что же с нашей левой сверткой? Мы ведь так и не написали для нее функции! Давайте сначала приведем три последние функции к общему виду, чтобы стало очевидно, где у них общность:

hoo [] acc = acc

hoo (x:xs) acc = hoo xs (if x < acc then x else acc)

doo [] acc = acc

doo (x:xs) acc = doo xs (if x > 0 then acc+1 else acc)

zoo [] acc = acc

zoo (x:xs) acc = zoo xs (x:acc)

Что общего у всех этих функций? Они идут по своим спискам, держа в уме текущее значение аккумулятора, и при обработке каждого элемента вызывают себя рекурсивно, заменяя текущее значение аккумулятора. Как заменяя? Что такого общего есть у всех трех этих функциях в тех трех выражениях в правой части, которые как раз и отличаются? А все эти три выражения есть какая-то функция от текущего элемента и аккумулятора! И именно эту функцию мы и вынесем в параметры как функцию f:

foldl f z [] = z

foldl f z (x:xs) = foldl f (f z x) xs

Вот теперь мы можем довершить переписывание наших функций через свертки:

hoo xs = foldl min (head xs) xs

doo xs =

foldl (\ acc x -> if x > 0 then acc+1 else acc) 0 xs

zoo xs = foldl (flip (:)) [] xs