Пока или регенерация хвоста в F #, что использовать когда?

Хорошо, только в F #, и вот как я это понимаю сейчас:

Поэтому мой вопрос: поскольку F # также поддерживает императивную парадигму, вы бы использовали хвостовую рекурсию в F # для проблем, которые не являются естественно рекурсивными? Тем более, что я прочитал, что компилятор реконструирует хвостовую рекурсию и просто превращает его в цикл while?

Если да: почему?

Лучший ответ – «ни». 🙂

Существует некоторая уродство, связанное с циклами и контурами хвостов.

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

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

Лучшим ответом является использование ни циклов, ни рекурсии. Функции более высокого порядка и лямбды – ваши спасители здесь, особенно карты и складки. Зачем обманывать грязными структурами управления для циклизации, когда вы можете инкапсулировать те, которые находятся в библиотеках многократного использования, а затем просто сформулировать суть ваших вычислений просто и декларативно?

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

Для тех, кто хочет узнать больше о сложениях в F #, почему бы не проверить мои первые три сообщения в блоге в серии по этой теме?

В порядке предпочтения и общего стиля программирования я напишу код следующим образом:

Карта / свернуть, если она доступна

let x = [1 .. 10] |> List.map ((*) 2) 

Его просто удобно и легко использовать.

Рекурсивная функция без хвоста

 > let rec map f = function | x::xs -> fx::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] 

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

Помните, что log 2 (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 fl = let rec loop acc = function | [] -> rev acc | x::xs -> loop (fx::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 <| fx::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 Lisp, но я думаю, что те случаи, когда CSP фактически упрощают алгоритмы, немногочисленны и далеки друг от друга. В комментариях приветствуются встречные примеры.

Хотя петли / для циклов

Мне приходит в голову, что, помимо понимания последовательности, я никогда не использовал while или для циклов в своем коде F #. В любом случае…

 > let map fl = 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 .

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

В общем, я использовал бы функциональную технику, где это возможно, на функциональном языке. Циклы никогда не функционируют, поскольку они исключительно полагаются на побочные эффекты. Поэтому, когда речь идет о императивном коде или алгоритмах, использование циклов является адекватным, но в функциональном контексте они не считаются очень приятными.

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

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

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

Я считаю, что вы должны придерживаться хвостовых вызовов почти во всех случаях, когда вы должны писать явный цикл. Это просто универсальнее:

  • Цикл while ограничивает вас одним телом цикла, в то время как хвостовой вызов позволяет вам переключаться между многими разными состояниями, пока выполняется «цикл».
  • Цикл while ограничивает вас одним условием для проверки завершения, с хвостовой рекурсией вы можете иметь произвольно сложное выражение соответствия, ожидающее отключения streamа управления от другого места.
  • Ваш хвост вызывает все возвращаемые полезные значения и может создавать полезные ошибки типа. Цикл while не возвращает ничего и полагается на побочные эффекты для выполнения своей работы.
  • Хотя циклы не являются первоclassными, тогда как функции с хвостовыми вызовами (или в то время как циклы в них). Рекурсивные привязки в локальной области могут быть проверены для их типа.
  • Рекурсивную функцию хвоста можно легко разбить на части, которые используют хвостовые вызовы для вызова друг друга в нужной последовательности. Это может облегчить чтение и поможет, если вы обнаружите, что хотите начать посередине цикла. Это не относится к циклу while.

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

Я бы сказал, что вы должны использовать только петли для случаев ниши, где цикл while идеально подходит для работы и относительно короткий. Во многих императивных языках программирования, в то время как петли часто скручиваются в неестественные роли, такие как вождение материала повторно над заявлением случая. Избегайте таких вещей и посмотрите, можете ли вы использовать хвостовые звонки или, что еще лучше, функцию более высокого порядка, чтобы достичь тех же целей.

для проблем, которые не являются естественно рекурсивными .. просто преобразует его в цикл while в любом случае

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

Давайте будем гением компьютера.