> А, что он не умеет рекурсии превращать в циклы?
Замечательно умеет, попробуйте например
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
А вот так вот, блин. Дальше оптимизации хвостовой рекурсии ни одна реализация ни одного известного мне языка не продвинулась, ни один компилятор не может нормально свести нехвостовую рекурсию к хвостовой, даже в простейших случаях. Всё надо делать руками, в лучших традициях Си и машинных кодов, а потом ещё говорят о красоте и выразительности ФЯП.
Не знаю, зачем, лол. Если человек способен понять, что случай тривиален, и что факториал и числа фибоначчи сводятся к простому циклу, то и умная машина вполне способна это сделать. Другое дело, что нормальных алгоритмов такой оптимизации до сих пор не существует, всё до сих пор на уровне пристального вглядывания, и это удручает.