[haskell] хвостовая рекурсия.

fact n = product [1..n]

?

это замечательно, но меня сейчас интересует не факториал, а сам вопрос про хвостовую рекурсию. то есть почему в первом случае - это оно, а во втором не оно.

У меня на милионе что то, что то тормозит. А вобще оба описания хвостовые, между ними различие только в вызове.

Что такое память не ест и работает шустро? У меня например быстро работает второй вариант (быстро переполняет стек и всё).

По идее, оба варинта эквиваленты. Вообще, у тебя много ресурсов тратится на цепочку отложенных вычислений. Надо так:

fact(0,n)=n
fact(x,n)=x`seq`n`seq`fact(x-1,n*x)

Либо google://haskell bang patterns

> буддисты, просветите.

все буддисты давно на лиспе сидят.

если собрать ghc что-нибудь без флагов, компилятор заменит обычную рекурсию хвостовой? я, кажется, нашёл где собака зарыта.

Заменит. Я тебе уже сказал в чем проблема.

твой вариант работает просто отлично. спасибо. посоветуй годную литературу ещё, пожалуйста.

Т.е. в первом случае компилятор оптимизирует рекурсию, а во втором нет? Так чтоли?

>твой вариант работает просто отлично. спасибо. посоветуй годную литературу ещё, пожалуйста.

Дык про принудительное вычисление выражений (`seq`) ещё в начале RWH написано, см. Space leaks and strict evaluation http://book.realworldhaskell.org/read/functional-programming.html

Не надо извращений. Строгого фолда вполне достаточно. А по хорошему в библиотеке должен быть строгий вариант product

foldl' (*) [1..n]

В качестве обзорного введения в язык подойдет методичка http://natahaus.ifolder.ru/3273553, хотя в ней о много не сказано. Ну а дальше, как тут уже советовали, Real World Haskell + HaskellWiki.

Не надо извращений. Строгого фолда вполне достаточно. А по хорошему в библиотеке должен быть строгий вариант product

Спорить не буду, но автор интересовался не лучшим способом вычислить факториал, а тем, почему не работает его реализация, которая, кстати, тоже имеет право на жизнь.

> Спорить не буду, но автор интересовался не лучшим способом вычислить факториал, а тем, почему не работает его реализация, которая, кстати, тоже имеет право на жизнь.

проверил в винхр (ghc 6.10.4) и в убунте 10.04 с только что установленым ghc — оба варианта fact выдают в общем-то одинаковые результаты

хм,а чем эти варианты отличаются от рекурсивной функции с одним аргументом, за исключением того, что менее понятные? //haskell не знаю

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

>Видимо тем что рекурсия у функции с одним аргументом не хвостовая

Хвостовая рекурсия
Материал из Википедии — свободной энциклопедии
Случай рекурсии, когда рекурсивный вызов функции происходит в конце её работы...

fac 0 = 1
fac x = x * fac (x-1)

Чем не хвостовая?

Здесь написано следующее, если немного расписать:

fac x = let x' = x - 1
            f' = fac x'
        in x * f'

>Т.е. последний вызов - умножение. Поэтому рекурсия не хвостовая.

Спасибо за объяснение. Я почему-то не вижу таких тривиальных вещей :(

> fac x = x * fac (x-1)

Чем не хвостовая?

Инфиксная запись не нужна >.<

Вызов в конце, но последней операцией будет умножение, а не вызов fac.

Другое дело префиксная:

(* x (fac (- x 1)))

Здесь сразу видно что корнем вычислений стоит никакой не вызов, а умножение.

Да дело-то не в записи. Я просто могу не замечать совсем очевидных вещей.

PS А формулы в lisp'e просто ужасно выглядят.