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

[metaclass]

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

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

Comments

[mchrome-cat.livejournal.com]

Кстати, существует книжка от Andrew Appel - "Compiling with continuations", где он по идее (я сам не читал) подробно рассказывает, зачем нужен cps.