Хотя или хвостовой рекурсии в F#, что использовать, когда?
Хорошо, только в F#, и вот как я понимаю это сейчас:
Некоторые проблемы носят рекурсивный характер (создание или считывание трееструктуры, чтобы назвать только одну), а затем вы используете рекурсию. В этих случаях предпочтительно использовать хвостовую рекурсию, чтобы дать стеку перерыв
Некоторые языки являются чисто функциональными, поэтому вы должны использовать рекурсию вместо циклов while, даже если проблема не является рекурсивной по своей природе.
Итак, мой вопрос: поскольку F# также поддерживает императивную парадигму, вы бы использовали хвостовую рекурсию в F# для задач, которые не являются естественно рекурсивными? Тем более, что я прочитал, что компилятор распознает хвостовую рекурсию и в любом случае просто преобразует ее в цикл while?
Если так: почему?
5 ответов
Лучший ответ - "нет".:)
Есть некоторое уродство, связанное как с циклом while, так и с хвостовой рекурсией.
В то время как циклы требуют изменчивости и эффектов, и хотя я не имею ничего против их использования в умеренных количествах, особенно когда они инкапсулированы в контексте локальной функции, иногда вы чувствуете, что загромождаете / унижаете свою программу, когда начинаете вводить эффекты просто в цикл,
Хвостовая рекурсия часто имеет тот недостаток, что требует дополнительного параметра аккумулятора или стиля прохождения продолжения. Это загромождает программу дополнительным шаблоном для массажа условий запуска функции.
Лучший ответ - не использовать ни циклы while, ни рекурсию. Функции высшего порядка и лямбды - ваши спасители, особенно карты и сгибы. Зачем дурачиться с беспорядочными структурами управления для циклов, когда вы можете инкапсулировать их в многократно используемые библиотеки, а затем просто и декларативно изложить суть ваших вычислений?
Если вы привыкли часто вызывать карту / сложение, а не использовать циклы / рекурсию, а также предоставлять функцию сгиба вместе с любым новым типом данных, представленных в древовидной структуре, вы далеко пойдете.:)
Для тех, кто хочет узнать больше о складках в F#, почему бы не проверить мои первые три сообщения в блоге в серии на эту тему?
В порядке предпочтений и общего стиля программирования я напишу код следующим образом:
Карта / сгиб, если она доступна
let x = [1 .. 10] |> List.map ((*) 2)
Это просто удобно и просто в использовании.
Нехвостая рекурсивная функция
> let rec map f = function
| x::xs -> f x::map f xs
| [] -> [];;
val map : ('a -> 'b) -> 'a list -> 'b list
> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
Большинство алгоритмов легче читать и выражать без хвостовой рекурсии. Это работает особенно хорошо, когда вам не нужно выполнять слишком глубокое повторение, что делает его подходящим для многих алгоритмов сортировки и большинства операций с сбалансированными структурами данных.
Помните, log2(1 000 000 000 000 000) ~= 50, поэтому операция log(n) без хвостовой рекурсии совсем не страшна.
Хвост-рекурсивный с аккумулятором
> let rev l =
let rec loop acc = function
| [] -> acc
| x::xs -> loop (x::acc) xs
loop [] l
let map f l =
let rec loop acc = function
| [] -> rev acc
| x::xs -> loop (f x::acc) xs
loop [] l;;
val rev : 'a list -> 'a list
val map : ('a -> 'b) -> 'a list -> 'b list
> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
Это работает, но код неуклюж, и элегантность алгоритма слегка затенена. Приведенный выше пример не так уж плох для чтения, но как только вы попадаете в древовидные структуры данных, это действительно становится кошмаром.
Хвост-рекурсивный с продолжением прохождения
> let rec map cont f = function
| [] -> cont []
| x::xs -> map (fun l -> cont <| f x::l) f xs;;
val map : ('a list -> 'b) -> ('c -> 'a) -> 'c list -> 'b
> [1 .. 10] |> map id ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
Всякий раз, когда я вижу код, подобный этому, я говорю себе: "Теперь это ловкий трюк!". Ценой читабельности он поддерживает форму нерекурсивной функции и нашел ее действительно интересной для хвостовых рекурсивных вставок в двоичные деревья.
Возможно, это моя монадофобия, говорящая здесь, или, может быть, мое внутреннее отсутствие знакомства с вызовом /cc Лиспа, но я думаю, что случаи, когда CSP на самом деле упрощает алгоритмы, немногочисленны. Контрпримеры приветствуются в комментариях.
Пока петли / для петель
Мне приходит в голову, что, кроме понимания последовательности, я никогда не использовал циклы while или for в своем коде F#. В любом случае...
> let map f l =
let l' = ref l
let acc = ref []
while not <| List.isEmpty !l' do
acc := (!l' |> List.hd |> f)::!acc
l' := !l' |> List.tl
!acc |> List.rev;;
val map : ('a -> 'b) -> 'a list -> 'b list
> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
Это практически пародия на императивное программирование. Вы могли бы быть в состоянии сохранить немного здравомыслия, объявив let mutable l' = l вместо этого, но любая нетривиальная функция потребует использования ref,
Честно говоря, любая проблема, которую вы можете решить с помощью цикла, уже является естественно рекурсивной, поскольку в конце вы можете перевести оба перехода (обычно условные) в переходы.
Я считаю, что вы должны придерживаться хвостовых вызовов почти во всех случаях, когда вы должны написать явный цикл. Это просто более универсально:
- Цикл while ограничивает вас одним телом цикла, а хвостовой вызов может позволить вам переключаться между многими различными состояниями во время работы цикла.
- Цикл while ограничивает вас одним условием проверки завершения, а с помощью хвостовой рекурсии вы можете иметь произвольно сложное выражение соответствия, ожидающее отключения потока управления где-то еще.
- Все ваши хвостовые вызовы возвращают полезные значения и могут вызвать полезные ошибки типа. Цикл while ничего не возвращает и использует побочные эффекты для своей работы.
- Хотя циклы не являются первым классом, в то время как функции с хвостовыми вызовами (или пока циклы в них) являются. Рекурсивные привязки в локальной области видимости могут быть проверены на предмет их типа.
- Хвостовая рекурсивная функция может быть легко разбита на части, которые используют хвостовые вызовы для вызова друг друга в необходимой последовательности. Это может упростить чтение и поможет, если вы захотите начать с середины цикла. Это не относится к циклу while.
В общем, циклы while в F# имеют смысл только в том случае, если вы действительно собираетесь работать с изменяемым состоянием внутри тела функции, повторяя одно и то же до тех пор, пока не будет выполнено определенное условие. Если цикл в целом полезен или очень сложен, вы можете включить его в какую-то другую привязку верхнего уровня. Если сами типы данных являются неизменяемыми (многие типы значений.NET), вы все равно можете получить очень небольшую выгоду от использования изменяемых ссылок на них.
Я бы сказал, что вы должны прибегать к циклам while только в тех нишевых случаях, когда цикл while идеально подходит для работы и относительно короток. Во многих императивных языках программирования циклы часто скручиваются в неестественные роли, такие как неоднократное вождение материала над оператором case. Избегайте подобных вещей и посмотрите, можете ли вы использовать хвостовые вызовы или, что еще лучше, функцию более высокого порядка для достижения тех же целей.
Многие проблемы носят рекурсивный характер, но долгое размышление с императивом часто мешает нам увидеть это.
В общем, я бы использовал функциональную технику везде, где это возможно, на функциональном языке - циклы никогда не бывают функциональными, поскольку они основаны исключительно на побочных эффектах. Поэтому, когда имеешь дело с императивным кодом или алгоритмами, использование циклов является адекватным, но в функциональном контексте они не считаются очень хорошими.
Функциональная техника означает не только рекурсию, но и использование соответствующих функций высшего порядка.
Таким образом, при суммировании списка, ни цикл for, ни рекурсивная функция, а fold это решение для того, чтобы иметь понятный код, не изобретая колесо.
для задач, которые не являются рекурсивными по природе... просто преобразуйте их в цикл while
Вы сами ответили на это. Используйте рекурсию для рекурсивных задач и цикл для вещей, которые не являются функциональными по своей природе. Просто всегда думайте: что кажется более естественным, а что более читабельным.