GHC, fibonacci, почему так медленно?

Извиняюсь:

fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)

Еще разок:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

Нет, оно не должно быстро работать. Это самый простой и медленный способ вычислять числа Фибоначчи.

Он везде будет работать медленно, потому что для каждого члена нужно вычислить два предыдущих - а для них еще два, и еще два...
При этом уже вычисленные значения не сохраняются, а вычисляются заново - оттуда тормоза.
Самый быстрый вариант из всех, что я видел:

fibs  = 0:1:zipWith (+) fibs (tail fibs)
fib n = fibs !! n

В этом случае значения вычисляются только один раз (наверное:)).
fib 100 вычисляется мгновенно.

http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

http://en.wikipedia.org/wiki/Memoization

Ладно, тогда самый быстрый вариант из рекурсивных.

эта форма хороша для теоретических оценок, но считать ее ты в флоатах будешь?

Самая лучший способ вычисления фибоначей, это:

[ 0 1 ]^N * [ 1 ] 
[ 1 1 ]     [ 1 ]

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

а какое отношение к скорости выполнения этого алгоритма имеет чистота языка ? или его функциональность ?

Ну какбе оптимизация хвостовой рекурсии бла-бла...

>Ну какбе оптимизация хвостовой рекурсии бла-бла...

А где тут хвостовая рекурсия?

> Ну какбе оптимизация хвостовой рекурсии бла-бла...

здесь нужна мемоизация

> А где тут хвостовая рекурсия?

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

обычную превращать в хвостовую? Нет.

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

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

>В данном случае...и в этом проблема

в данном случае проблема не в компиляторе, а в ДНК. впрочем, это моё личное мнение

Дожили. Уже в хаскель быдлокодеры пошли.