До этого игрался с F#, решил поближе познакомиться с Haskell.
Смотрю исходники Haskell и возник вопрос по поводу хвостовой рекурсии.
Например, код для вычисления длины списка.
-- | The 'genericLength' function is an overloaded version of 'length'. In
-- particular, instead of returning an 'Int', it returns any type which is
-- an instance of 'Num'. It is, however, less efficient than 'length'.
genericLength :: (Num i) => [b] -> i
genericLength [] = 0
genericLength (_:l) = 1 + genericLength l
Если бы я писал на F#, то сделал бы рекурсию с аккумулятором, чтобы на стеке точно ничего не оставалось и рекурсия была хвостовой. В Haskell, смотрю, с этим как-то осбенно не заморачиваются.
Это из-за ленивости языка и его способности преобразовывать такую рекурсию в хвостовую?
Общий вопрос: как писать рекурсии на Haskell, чтобы быть уверенным в том, что он сделает рекурсию хвостовой?
Потому что, если бы я в F# написал:
let rec length = function
| [] -> 0
| _ :: tail -> 1 + length tail
Здравствуйте, Димчанский, Вы писали:
Д>Это из-за ленивости языка и его способности преобразовывать такую рекурсию в хвостовую?
0) Никакого преобразования в хвостовую рекурсию не происходит. Хвостовая рекурсия в ленивом языке далеко не лучший вариант, к которому нужно стремиться. См. тут
, например.
1) Если в строгом ФЯ все крутится вокруг "как бы нам тут сделать хвостовую рекурсию" в ленивом ФЯ более важная концепция — guarded recursion, и вообще см. тут.
2) "Переполнение стека" в ghc-ном рантайме это переполнение особого участка кучи, ограничение можно установить каким угодно — только бы памяти хватило, существует оно скорее в диагностических целях. В этом ghc-ный рантайм похож скорее на sml/nj чем на F#. Но код, использующий большие объемы "стека", лучше не писать, хотя-бы по той причине, что он обычно тормозной, точнее практически всегда можно написать и побыстрее.
Д>Общий вопрос: как писать рекурсии на Haskell, чтобы быть уверенным в том, что он сделает рекурсию хвостовой?
Рекурсии вообще лучше не писать, а пользоваться стандартными комбинаторами.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Спасибо за развернутый ответ и ссылки. Прочитал все, но у меня остались все же некоторые неясности.
K>Но код, использующий большие объемы "стека", лучше не писать, хотя-бы по той причине, что он обычно тормозной, точнее практически всегда можно написать и побыстрее.
С точки зрения, что код, использующий большие объемы стека, лучше не писать, можно сделать вывод, что длину списка лучше вычислять, например, так:
lengthAux :: (Num i) => i -> [b] -> i
lengthAux n [] = n
lengthAux n (_:l) = lengthAux (n+1) l
length' :: (Num i) => [b] -> i
length' = lengthAux 0
На стек ничего не кладется, код написан так, чтобы не использовать большие объемы "стека".
Чем это хуже?
По последней ссылке есть такие слова:
In many programming languages, calling a function uses stack space, so a function that is tail recursive can build up a large stack of calls to itself, which wastes memory. Since in a tail call, the containing function is about to return, its environment can actually be discarded and the recursive call can be entered without creating a new stack frame. This trick is called tail call elimination or tail call optimisation and allows tail-recursive functions to recurse indefinitely.
In Haskell, the function call model is a little different, function calls might not use a new stack frame, so making a function tail-recursive typically isn't as big a deal—being productive, via guarded recursion, is more usually a concern.
Хочется понять физику. Чем модель вызова фукций в Хаскеле отличается от других языков.
K>Рекурсии вообще лучше не писать, а пользоваться стандартными комбинаторами.
Ну нужно начать что-то писать, чтобы почувствовать, как можно избегать рекурсий. Потому что пока не чувствую, как можно совсем без рекурсий.
Приводить к хвосторекурсивной форме и форсировать ленивость в общем случае не совсем корректно, потому что натуральные числа могут быть заданы как data Nat = Zero | Succ Nat и нам может захотеться, чтобы такое число начинало строиться с Zero, ставя каждое следующее число в соответсвие следующему элементу списка.
Здравствуйте, Димчанский, Вы писали:
Д>Спасибо за развернутый ответ и ссылки. Прочитал все, но у меня остались все же некоторые неясности.
K>>Но код, использующий большие объемы "стека", лучше не писать, хотя-бы по той причине, что он обычно тормозной, точнее практически всегда можно написать и побыстрее.
Д>С точки зрения, что код, использующий большие объемы стека, лучше не писать, можно сделать вывод, что длину списка лучше вычислять, например, так:
Д>
lengthAux :: (Num i) => i -> [b] -> i
Д>lengthAux n [] = n
Д>lengthAux n (_:l) = lengthAux (n+1) l
Д>length' :: (Num i) => [b] -> i
Д>length' = lengthAux 0
Д>
Д>На стек ничего не кладется, код написан так, чтобы не использовать большие объемы "стека". Д>Чем это хуже?
"Ничего" не пойдёт на стек, если сделаем, например, так:
{-# LANGUAGE BangPatterns #-}
lengthAux :: (Num i) => i -> [b] -> i
lengthAux n [] = n
lengthAux !n (_:l) = lengthAux (n+1) l
Здравствуйте, Димчанский, Вы писали:
Д>Прочитал все, но у меня остались все же некоторые неясности.
Это совершенно нормально. Дальше неясностей станет только больше.
Д>С точки зрения, что код, использующий большие объемы стека, лучше не писать, можно сделать вывод, что длину списка лучше вычислять, например, так: Д>
lengthAux :: (Num i) => i -> [b] -> i
Д>lengthAux n [] = n
Д>lengthAux n (_:l) = lengthAux (n+1) l
Д>length' :: (Num i) => [b] -> i
Д>length' = lengthAux 0
Д>
Д>На стек ничего не кладется, код написан так, чтобы не использовать большие объемы "стека".
Дело в том, что n+1 в этом коде ничего и не делает, кроме занимания все больших объемов. Язык-то ленивый. Это, по крайней мере, справедливо для Int, Integer, Double и прочих ходовых инстансов Num.
Д>Хочется понять физику. Чем модель вызова фукций в Хаскеле отличается от других языков.
"Немного отличается" — это сильное преуменьшение. Чтоб понимать "физику" нужно читать это и далее по ссылкам. Но для написания программ на хаскеле это все, к счастью, не обязательно. По крайней мере, не для первого чтения.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Это совершенно нормально. Дальше неясностей станет только больше.
Это обнадеживает.
K>Дело в том, что n+1 в этом коде ничего и не делает, кроме занимания все больших объемов. Язык-то ленивый.
Вооот, теперь понятно. После энергичного F# совершенно об этом забыл. Если переписать в терминах F#, то там в аккумуляторе будет формироваться длинная цепочка Lazy объектов с каждым инкрементом.
K>"Немного отличается" — это сильное преуменьшение. Чтоб понимать "физику" нужно читать это и далее по ссылкам. Но для написания программ на хаскеле это все, к счастью, не обязательно. По крайней мере, не для первого чтения.
Ну "little different" это их же слова, мопед не мой.
Re[4]: [Haskell] Хвостовая рекурсия
От:
Аноним
Дата:
15.02.12 07:43
Оценка:
Здравствуйте, Курилка, Вы писали:
К>"Ничего" не пойдёт на стек, если сделаем, например, так:
К>
К>{-# LANGUAGE BangPatterns #-}
К>lengthAux !n (_:l) = lengthAux (n+1) l
Форсировать n тут совсем ни к чему. Оно и так будет форсированно плюсом. Так что оба варианта эквивалентны (даже на уровне Core, по крайней мере при компиляции в GHC 7.0.3).
Re[5]: [Haskell] Хвостовая рекурсия
От:
Аноним
Дата:
15.02.12 09:45
Оценка:
Здравствуйте, Аноним, Вы писали:
А>Форсировать n тут совсем ни к чему. Оно и так будет форсированно плюсом.
Ан нет. Глупость конечно же написал. Эквивалентны эти примеры только с -O компиляции (за счет анализатора строгости), а без оного нужно форсировать либо !-ом либо seq-ом.
lengthAux :: (Num i) => i -> [b] -> i
lengthAux n [] = n
lengthAux n (_:l) = n `seq` lengthAux (n+1) l
