В то время как или Хвостовая рекурсия в 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]

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

Помните, 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 loops / for loops

Мне пришло в голову, что, Помимо понимания последовательностей, я никогда не использовал циклы 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

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

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

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

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

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