![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Принудительная хвостовая рекурсия: жрать память вместо стека?
Читаю про катаморфизмы и 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?
no subject
Там вместо того, чтобы сделать нормальный foldr, с помощью foldl строилось замыкание, которое потом сделает foldr.
Так вот, это замыкание для своего *выполнения* требует такого же линейного объема *стека*, а не кучи (а само по себе еще и занимает место в куче).
no subject
Посмотрел еще раз пример FoldBack. Вроде бы, выглядит логично (но куда проще было бы взять и переписать все через надежный Async :). Только unit как возвращаемый тип несколько беспокоит меня. Если я правильно понял тот комментарий разработчиков F#, то такое продолжение как в статье может запросто съесть и стек на некоторых версиях .NET, а может и сработать как надо.
no subject