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