![[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
no subject
"От Радослава ко Хотеславу. возьми у прасола 2 гривене и 5 куно". (1-я стр.).
"Якове брате, еби лежа, ебехото, аесово".(2-я строчка)
"Радослав дает указание своему брату Хотеславу: "Возьми у прасола (торговца) 2 гривны и 5 кун". Это указание Хотеславу резко не понравилось; возможно, брат отсылает его к прасолу вместо того, чтобы просто отдать долг (есть аналогии этой ситуации в новгородской грамоте 690). Он ответил язвительно и не стесняясь формой выражения. Обращение - "Якове брате" (а не Радославе) - по-видимому, ироническое или даже саркастическое. Хотеслав называет брата не мирским, а крестильным именем, да еще со словом брате; надо полагать, это было уместно лишь в церковной или в особо торжественной ситуации, но никак не в сочетании с последующей грубостью. Примерный смысл ответа - "не оригинальничай" (веди себя, как все).
no subject
no subject
no subject
no subject
Кстати, в исходниках Async есть забавный комментарий (там продолжения используются):
"F# don't always take tailcalls to functions returning 'unit' because this is represented as type 'void' in the underlying IL. Hence we don't use the 'unit' return type here, and instead invent our own type."
no subject
Там вместо того, чтобы сделать нормальный foldr, с помощью foldl строилось замыкание, которое потом сделает foldr.
Так вот, это замыкание для своего *выполнения* требует такого же линейного объема *стека*, а не кучи (а само по себе еще и занимает место в куче).
no subject
Посмотрел еще раз пример FoldBack. Вроде бы, выглядит логично (но куда проще было бы взять и переписать все через надежный Async :). Только unit как возвращаемый тип несколько беспокоит меня. Если я правильно понял тот комментарий разработчиков F#, то такое продолжение как в статье может запросто съесть и стек на некоторых версиях .NET, а может и сработать как надо.
no subject
no subject
no subject
Например, кое-где я использую формально типо-небезопасную библиотеку (хотя там с типами всё хорошо, но не доказано), но чуть более медленную, зато tail-recursive на всех функциях, работающих со списками.
no subject
no subject
no subject
no subject
Собственно, потому и не меняют List.map в stdlib, что текущая версия на мелких списках чудо как хороша. (а именно, с текущим мусорщиком лучше не сделать.)
А для больших объёмов рекомендуют не списки, а что-то побыстрее.
no subject
no subject
no subject
no subject
no subject
no subject