[Haskell] Хвостовая рекурсия
От: Димчанский Литва http://dimchansky.github.io/
Дата: 13.02.12 10:05
Оценка:
До этого игрался с 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


То, выполнение кода

length [1..10000000]


привело бы к StackOverflowException.
... << RSDN@Home 1.2.0 alpha 5 rev. 1536>>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.