Принудительная хвостовая рекурсия: жрать память вместо стека?

[metaclass]

Читаю про катаморфизмы и FSharp. Вообще, изначально это я искал ответ на этот вопрос, но зачитался и забыл.

Там приводится пример, как выразить foldBack (оно же foldr) через fold(оно же foldl) с помощью continuations. И выглядит это как будто мы заменяем использование стека в случае не-tail-recursive функции таким же использованием памяти из head. Причем в случае стека выделение и удаление памяти достаточно дешевое, а вот что будет в случае обычной памяти - вопрос загадочный. Непонятно, есть ли тогда какие-нибудь преимущества у такого преобразования не-tail-recursive функции в tail-recursive?

Comments

[gds.livejournal.com]

но на стеке -- быстрее, поэтому стандартный List.map выигрывает по скорости у алгоритма, выделяющего на хипе и далее небезопасно (Obj) меняющего cons cell. (хотя, в целом, всё получается безопасно, кодэ см. в extLib.)
Собственно, потому и не меняют List.map в stdlib, что текущая версия на мелких списках чудо как хороша. (а именно, с текущим мусорщиком лучше не сделать.)
А для больших объёмов рекомендуют не списки, а что-то побыстрее.