Оптимизация в Haskell (ghc)

Haskell optimizes tail recursion

нет

так вы двое друг другу противоречите -- если оптимайзит хвостовую -- значит превращает ее в цикл.

> А, что он не умеет рекурсии превращать в циклы?

Замечательно умеет, попробуйте например

frac :: Int -> Integer
frac n = fracAcc n 1
      where fracAcc 0 v = v
            fracAcc n v = (fracAcc $! (n-1)) $! (n*v)

в сравнении с 

frac 0 = 1
frac n = n * frac (n-1)

Для больших n

ну это из категории:

-не подскажете ли, сколько времени?

-нет, не подскажу

:)

Умеет, конечно.

Почему на коде типа

main = print(q(100000000000)) q(0) = 0 q(n) = n + q(n-1)

пишет, что не вмещается в 8Мб стека, для увеличения размера стека используйте параметр и т.д. ???

Попробуй так

http://www.haskell.org/haskellwiki/Performance/Accumulating_parameter

А как-нибудь без костылей можно?

костыль - это то как раз как ты считаешь: кладёшь н в стек, вызываешь ф-ию, кладёшь в стек (н-1), вызываешь функцию.

> костыль - это то как раз как ты считаешь: кладёшь н в стек, вызываешь ф-ию, кладёшь в стек (н-1), вызываешь функцию.

Почему? Есть рекурсивное определение того что надо. В математике нет аккумуляторов!

А вот так вот, блин. Дальше оптимизации хвостовой рекурсии ни одна реализация ни одного известного мне языка не продвинулась, ни один компилятор не может нормально свести нехвостовую рекурсию к хвостовой, даже в простейших случаях. Всё надо делать руками, в лучших традициях Си и машинных кодов, а потом ещё говорят о красоте и выразительности ФЯП.

Ну так иначе пришлось бы отдельно описывать, какие случаи достаточно тривиальны, чтобы компилятор их понял, а какие нет — зачем?

Не знаю, зачем, лол. Если человек способен понять, что случай тривиален, и что факториал и числа фибоначчи сводятся к простому циклу, то и умная машина вполне способна это сделать. Другое дело, что нормальных алгоритмов такой оптимизации до сих пор не существует, всё до сих пор на уровне пристального вглядывания, и это удручает.