Хвостовая рекурсия в Haskell

1. Не знаю - вообще заморачиваются, но реже -скажем пересаживать ++ на хвостовую рекурсию бесполезно - там не происходит наращивания стека - элементы вычисляют по мере необходимости (сама операция вообще выполняется за константное время)

2. Потому что foldr обязательно вычислит весь список, а foldl, если например он строит поэлементно новый список, будет вычисляться только по мере вычисления элемннтов из списка-результата (в частности foldl может быть осмысленно применен к бесконечному списку, а foldr - нет)

По второму пункту не дезинформируй общественность:

[vlm@nala:~]> ghc a.hs
[vlm@nala:~]> ./a.out 
"Got result"
[vlm@nala:~]> cat a.hs 
data List = Null | MkList Char List deriving Show
lhead (MkList 'a' _) = print "Got result"
main = lhead $ foldr MkList Null ['a'..]
[vlm@nala:~]>

1. premature optimization is the root of all evil. (c) Knuth. Более того, в lazy языке правила немножко другие.

2. В энергичном языке foldl хороший, потому что если мы вычисляем всё (а мы всегда вычисляем всё), то foldl может хорошо лечь на хвостовую рекурсию:

Вот простая левая свёртка на OCaml, языке энергичном:

let rec fold_left f acc = function
  | h::t -> fold_left f (f acc h) t
  | [] -> acc;;

Явно видно, что тут есть хвостовая рекурсия, и в энергичном языке этого нам бы хватило за глаза. fold_left является хорошим в энергичных языках, потому что он хвосторекурсивный. Раз мы всё равно вычисляем весь список целиком, то у нас вопросов больше к нему не возникает.

Однако, запишем то же самое на Хаскеле, на языке ленивом:

foldl f acc (x:xs) = foldl f (f acc x) xs
foldl f acc [] = acc

Здесь мы видим, что вроде бы хвостовая рекурсия есть, и нам нужно радоваться. Однако, что будет если мы попытаемся вычислить результат этой функции? Мы будем должны пройти весь список (хвостовой рекурсией, не иначе!), чтобы собрать вычисление вида

f (f (f acc0 x1) x2) xn

где x₁ — первый элемент списка, начиная с головы, x₂ — второй, и так далее.

Если язык ленивый, то мы будем тащить значение из внешней функции f (((...))) xn раньше, чем из остальных. И всегда вычислять полностью список, прежде чем вернуть результат. Мы построили эту серию вложенных функций f с помощью хвостовой рекурсии (тут проблем нет), но в ленивом языке нам ещё нужно вычислить саму эту вложенную последовательность!

Представим, что в качестве f мы подставили оператор создания ячейки списка: (:) :: a → [a] → [a], примерно так: foldl (flip (:)) [] "abc"
Хвосторекурсивно на Хаскель нам вычислит следующую последовательность:

(:) 'c' ((:) 'b' ((:) 'a' []))

или, что понятнее (чисто синтаксическая трансформация) но строго эквивалентно:

'c' : ('b' : ('a' : [])).

Теперь представим, что тот, кто вызывает foldl заинтересован посмотреть на первый элемент в получившемся списке: let x:xs = foldl (flip (:)) [] "abc". Что получится? Что мы быстро ему отдали 'c', а санк (недовычисленное тело) 'b' : ('a' : []), остался висеть в памяти. И чем больше список, тем длиннее и сложнее санк, который висит в памяти после foldl, до тех пор пока мы полностью не пройдёмся по результатам foldl и не вычислим его до самого остатка.

Вывод: хвосторекурсивность foldl'а нас не спасает: конструируем мы выражение хвосторекурсивно и замечательно (и в момент первого вызова foldl), но вот после этого конструирования у нас в памяти остаётся висеть развесистая клюква из санков, которые занимают циклы GC, которые могут быть «забыты» где-то в let-байндинге внешней по отношению к foldl функции, и будут продолжать доставлять нам неприятности.


> Однако, запишем то же самое на Хаскеле, на языке ленивом:
> foldl f acc (x:xs) = foldl f (f acc x) xs
> foldl f acc [] = acc
Я правильно понимаю, что foldl f $! (f acc x) xs избавит от кучи невычисиленных выражений и сделает обычную хвостовую рекурсию?

1. Есть библиотечная функция foldl', которая делает почти это.
2. Почти избавит. Вот смотри:


Prelude> Data.List.foldl' (\a (_:e:_) -> a + e) 0 [[1..], [2..], [3..]]
9
Prelude> fst (Data.List.foldl' (\(a, b) (e:xs) -> (a + e, xs:b)) (0,[]) [[1..], [2..], [3..]])
6
Prelude>


где здесь полностью произведённые вычисления? Санки-то висят в xs...

Дело в том, что $! (или seq) не вычисляет выражение целиком, а форсирует его до конструктора. Поэтому сколько либо развесистые санки останутся висеть в воздухе точно также.

Если ты используешь какую-нибудь простую операцию, типа плюса, то вычисление до конструктора поможет нехило...


Prelude> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
Prelude> Data.List.foldl' (+) 0 [1..1000000]
500000500000
Prelude>


...но если вычисляешь что-то посложней, будут такие же грабли, и придётся `seq` протаскивать дальше, внутрь функции f ad infinitum, чтобы получить бенефиты foldr.

Плюс, этот вариант foldl всё равно не будет работать с бесконечными списками.

Теперь посмотрим на то, что произойдёт, если ту же самую ленивую конструкцию сделать с правой свёрткой.

Для начала, опять же, возьмём энергичный язык OCaml:

let rec fold_right f list acc =
  match list of
    | h::t -> f h (fold_right f t acc)
    | [] -> acc;;

Мы наблюдаем печальную картину: никакой хвостовой рекурсии нет, и список проходится (никуда от этого не денешься в энергичном языке), из начала в конец, и только с конца начинается свёртка. Всё грустно.

Но стоит нам перейти в ленивый Хаскель, как всё меняется:

foldr f acc (x:xs) = f x (foldr f acc xs)
foldr f acc [] = acc

Вроде бы та же самая форма, как в ОКамле, да? Но обратите внимание, как эта форма работает в ленивом языке! Допустим, мы суём (:) в качестве функции: foldr (:) [] "abc". Получаем следующую конструкцию:

'a' : (foldr (:) [] "bc")

результат которой будет эквивалентен результату 'a' : ('b' : ('c' : [])), но только в «конце концов» — не сразу, постепенно.

Изначально мы имеем там, где подчёркнуто, один санк. Очень короткий и хороший санк, не древовидный как в случае с левой свёрткой, а очень простой: (foldr (:) [] "").

Если мы дёрнем эту ленивую конструкцию с помощью let _:_:xs = foldl (flip (:)) [] "abc", то мы получим 'a':'b':(foldr (:) [] "c"), где подчёркнут, опять же, очередной недовычисленный санк.

То есть, в двух очень похожих конструкциях на ленивых языках

let _:_:xs = foldl (flip (:)) [] "abcdef"
let _:_:xs = foldr (:) [] "abcdef"

мы в первой получим в xs очень санк ('d' : ('c' : ('b' : ('a' : [])))), развесистость и сложность которого зависит от длины списка, полученный с помощью торжественного и «эффективного» применения хвостовой рекурсии. Cлишком кавалерийского применения, надо сказать.
А вот во второй конструкции получим в xs очень компактное продолжение вида (foldr (:) [] "cdef"), которое практически не занимает места в памяти.

Этот пример демонстрирует, что в ленивых языках foldr кошернее: он позволяет осуществлять ленивые чтения из списка, полученного в результате правой свёртки, без затрат памяти на хранение санка. Левая свёртка нам даёт хвостовую рекурсию, но в результате неё мы имеем кашу в памяти из кучи недовычисленных санков.

Почти обратная ситуация в языках энергичных. Так как и fold_right, и fold_left вынуждены вычислять список полностью, то экономия недовычисленных не является проблемой, санок в энергичных языках нет (комрады, молчать). И единственная оптимизация и разница между ними (кроме порядка вычисления, что может быть важно вызывающему из-за коммутативности) состоит в том, используется ли хвостовая рекурсия, или нет.

Плюс ещё, убойный аргумент: с помощью правой свёртки foldr можно запрограммировать левую свёртку foldr, но не наоборот. Поэтому часто правая свёртка называется fold'ом, без l или r, как основная конструкция.

Обратим внимание, что конструкция вида foldr (:) [] (x1 : x2 : x3 : []) после и по мере вычисления эквивалентна (x1 : x2 : x3 : []), или, в общем случае, выражение foldr f [] (x1 : x2 : x3 : []) эквивалентно выражению x1 `f` x2 `f` x3 `f` []. Как видим, если функция f не строга по второму аргументу, то что мы сделали — это «заменили» все конструкторы (:) на вызов `f` в инфиксной форме. Это позволяет думать о правой свёртке как о методе заменить конструктор ячейки списка (:) на произвольное вычисление лениво.

Спасибо. Я начинаю понимать.

Но все ваши примеры возвращают списки, список можно лениво тянуть элемен за элементом.
А в случае fold (+) 0 [1..n] результат нам нужен весь и сразу.
И в этом случае я не понимаю, как может помочь ленивость, зато вижу явный выигрыш от хвостовой рекурсии.

А в этом случае и не нужна ленивость. Тут надо использовать foldl'.

Если, конечно, не используется какой-нибудь экзотический инстанс класса Integral, например, нумералы Пеано :) В этом случае ленивость была бы оправдана.

Супер-пост, огромное спасибо.

Пример:

Есть список

'a' : 'b' : 'c' : 'd' : []

Мы хотим сделать из него список вида

data List = Null | MkList Char List

Видно, что двоеточие (:) в вышеуказанном списке можно заменить на `MkList`, ибо MkList принимает два аргумента, левый из которых имеет нужный нам тип Char:

'a' `MkList` 'b' `MkList 'c' `MkList` 'd' &hellip а что же с последним элементом? А он есть Null.

Итого, функция ленивого, инкрементального, эффективного и совсем-совсем не деструктивно хвосторекурсивного преобразования базового списка в нашу новую структуру данных типа List выглядит так:

foldr MkList Null

или вот код полностью:

[vlm@nala:~]> ghc a.hs
[vlm@nala:~]> ./a.out 
MkList 'a' (MkList 'b' (MkList 'c' Null))
[vlm@nala:~]> cat a.hs
data List = Null | MkList Char List deriving Show
main = print $ foldr MkList Null "abc"
[vlm@nala:~]>

3. И как надо размышлять в терминах lazy evaluation, чтобы получить ответ на первые два вопроса.

Размышляй в терминах санок: любой вызов функции генерирует отложенное вычисление, если его результат не нужен. В итоге

f (foldr f [] "abc") не будет вычислять foldr, а только сделает санку (foldr f [] "abc") и попробует запустить первый f с ней в качестве аргумента.

Этот санк, концептуально, будет состоять из:

1. Ссылки на f (константный объем памяти — слово?)
2. Ссылки на [] (то же самое)
3. Ссылки на "abc", или даже какой-то ленивый бесконечный список, наверное взятый из родительского контекста (тоже константный объем памяти — ссылка на байндинг строки или списка из родительского контекста)
4. Пожелания запустить foldr (ссылка на foldr)

Поэтому это достаточно дешёвая сущность.

>>любой вызов функции генерирует отложенное вычисление, если его результат не нужен

А когда считается, что результат стал нужен? Если я правильно понимаю, то таким образом можно целую программу представить, как одно большое отложенное вычисление. Когда вычисление действительно происходит?

Единственный случай, когда производится "форсирование" санки - это (если санка принадлежит к алгебраическому типу) когда по ней выполняется case или (если она принадлежит к функциональному типу) когда форсируется результат аппликации ее к аргументу (кстати, в кодировке Чёрча эти два случая - одно и то же). Если подумать, то становится понятно, что это именно те случаи, когда форсирование нужно.

Пример:

Рассмотрим функцию length.

length [] = 0
length (x:xs) = 1 + length xs

Ее можно переписать так:

length xs = case xs of -- Тут будет (при форсировании санки length xs) форсирована санка xs
[] -> 0
(x:xs') -> 1 + length xs' -- case по элементу x не выполняется, поэтому сам элемент не будет форсирован


-- Списочный аргумент будет форсирован из-за pattern matching по нему
foldr f unit [] = unit
foldr f unit (x:xs) = x `f` (foldr unit xs) -- В этой ветке будет форсирован аргумент f (т.к. выполняется его аппликация). Это не значит, что будут форсированы x, unit или foldr unit xs.

Стоит напомнить, что "форсирование" выполняется до приведения к слабой заголовочной нормальной форме (WHNF), т.е. пока не выяснится конструктор санки (если она алгебраического типа) или не-знаю-как-получше-сказать (если она функционального).



В программе main = putStrLn "Hello world" рантаймом форсируется санка main, в процессе чего putStrLn форсирует хребет переданного списка символов (когда определяет, надо ли напечатать еще один символ) и его элементы (когда определяет, какой конкретно char надо запихать в fputc).

Спасибо. Теперь яснее. А когда происходит форсирование арифметических типов? Ведь для них нет ни pattern matching ни аппликации.

Когда вычисляется тот же:
1 + length xs

Я пытаюсь выяснить имеет ли смысл хвостовая рекурсия хотя бы для length xs.

Форсирование арифметических типов это тоже pattern matching. Они реализованы примерно как

data Int = I# { unboxedValue :: Int# }

Если же вопрос и был задан про unboxed типы Int# итп. - то они просто вообще не ленивы, т.е. реализованы с помощью обыкновенных "сишных" значений, а не санок.

Хвостовая рекурсия для length смысла не имеет; честно говоря, не понимаю, как ответ на этот вопрос зависит от способа форсирования арифметических типов.

Спасибо. Я нашел ответ на свой следующий вопрос
http://www.haskell.org/haskellwiki/Performance/Accumulating_parameter

думаю будет понятнее, если почитать про graph reduction: http://en.wikibooks.org/wiki/Haskell/Graph_reduction

length, конечно, хвостатый

1. заморачиваются там, где это нужно. в функциях, возвращающих ленивые структуры данных (список, например), это не нужно и, более того, вредно.

2. по этой же самой причине. довольно подробно написано в хаскелевой вики:
http://www.haskell.org/haskellwiki/Stack_overflow
http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl'

Спасибо за ссылки.