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

Ответ 1

Лучший ответ - "ни".:)

Там какое-то уродство ассоциируется как с петлями, так и с хвостовой рекурсией.

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

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

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

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

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

Ответ 2

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

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

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]

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

Помните, log ₂ (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]

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

Вероятно, моя монад-фобия говорит здесь, или, может быть, мое незнакомое знакомство с Lisp call/cc, но я думаю, что те случаи, когда CSP фактически упрощают алгоритмы, немногочисленны и далеко друг от друга. Контр-примеры приветствуются в комментариях.

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

Мне кажется, что, помимо понимания последовательности, я никогда не использовал while или для циклов в своем коде 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.

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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