F # хвост рекурсии и почему бы не написать цикл while?

Я изучаю F # (новичок в функциональном программировании в целом, хотя использовал функциональные аспекты С# в течение многих лет, но пусть сталкивается с этим, это довольно разные), и одна из вещей, которые я прочитал, заключается в том, что компилятор F # идентифицирует хвостовую рекурсию и компилирует его в цикл while (см. http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).

То, что я не понимаю, - это то, почему вы должны писать рекурсивную функцию вместо цикла while, если это то, во что она превратится. Особенно учитывая, что вам нужно сделать дополнительную работу, чтобы сделать вашу функцию рекурсивной.

У меня есть чувство, что кто-то может сказать, что цикл while не особенно функциональен, и вы хотите действовать все функционально, а что-то не так, как вы используете рекурсию, но почему же для этого достаточно, чтобы компилятор превратил его в цикл while?

Может кто-нибудь объяснить это мне?

Ответ 1

Вы можете использовать тот же аргумент для любого преобразования, которое выполняет компилятор. Например, когда вы используете С#, вы когда-нибудь используете лямбда-выражения или анонимные делегаты? Если компилятор просто превратит их в классы и (не анонимные) делегаты, то почему бы просто не использовать эти конструкции самостоятельно? Аналогично, вы когда-либо использовали блоки итераторов? Если компилятор просто превратит их в государственные машины, которые явно реализуют IEnumerable<T>, то почему бы просто не написать этот код самостоятельно? Или, если компилятор С# просто собирается испускать IL в любом случае, зачем писать С# вместо IL в первую очередь? И так далее.

Один очевидный ответ на все эти вопросы заключается в том, что мы хотим написать код, который позволяет нам четко выражать себя. Аналогично, существует множество алгоритмов, которые являются естественно рекурсивными, поэтому запись рекурсивных функций часто приводит к явному выражению этих алгоритмов. В частности, возможно, легче рассуждать о завершении рекурсивного алгоритма, чем цикл while во многих случаях (например, существует ли явный базовый случай и каждый рекурсивный вызов делает проблему "меньшей"?).

Однако, поскольку мы пишем код, а не математическую документацию, неплохо также иметь программное обеспечение, которое соответствует определенным критериям реальной работы (например, способность обрабатывать большие входы без). Таким образом, тот факт, что хвостовая рекурсия преобразуется в эквивалент цикла while, является критическим для возможности использования рекурсивных формулировок алгоритмов.

Ответ 2

Рекурсивная функция часто является наиболее естественным способом работы с определенными структурами данных (такими как деревья и списки F #). Если компилятор хочет преобразовать мой естественный, интуитивно понятный код в неудобный цикл while по соображениям производительности, который прекрасен, но зачем мне это писать?

Кроме того, здесь подходит Брайан ответ на соответствующий вопрос. Функции более высокого порядка часто заменяют как циклы, так и рекурсивные функции в вашем коде.

Ответ 3

Тот факт, что F # выполняет оптимизацию хвоста, - это просто деталь реализации, которая позволяет использовать хвостовую рекурсию с той же эффективностью (и не бояться) как цикл while. Но именно это - деталь реализации - на поверхности ваш алгоритм все еще рекурсивный и структурирован таким образом, что для многих алгоритмов является наиболее логичным, функциональным способом его представления.

То же самое относится к некоторым внутренним элементам обработки списка, а также к F # - внутренняя мутация используется для более эффективной реализации манипулирования списками, но этот факт скрыт от программиста.

В чем дело, так это то, как язык позволяет вам описать и реализовать свой алгоритм, а не какую механику использовать под капотом, чтобы это произошло.

Ответ 4

Цикл

A while является обязательным по своей природе. В большинстве случаев при использовании циклов while вы обнаружите, что пишете такой код:

let mutable x = ...
...
while someCond do
    ...
    x <- ...

Этот шаблон распространен в императивных языках, таких как C, С++ или С#, но не так распространен в функциональных языках.

Как и другие плакаты, некоторые структуры данных, более точно рекурсивные структуры данных, поддаются рекурсивной обработке. Поскольку наиболее распространенная структура данных в функциональных языках является безусловно связанным списком, решение проблем с использованием списков и рекурсивных функций является обычной практикой.

Другой аргумент в пользу рекурсивных решений - это тесная связь между рекурсией и индукцией. Использование рекурсивного решения позволяет программисту мыслить о проблеме индуктивно, что, возможно, помогает в ее решении.

Опять же, как утверждают другие плакаты, тот факт, что компилятор оптимизирует хвостовые рекурсивные функции (очевидно, не все функции могут извлечь выгоду из оптимизации хвостового вызова), представляет собой деталь реализации, которая позволяет вашему рекурсивному алгоритму работать в постоянном пространстве.