Список фрагментов функционального кода для процедурных программистов? [закрыто]

(Отредактировано из этого сообщения на fshub )

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

Это возникло, когда некоторое время назад играли с алгоритмами сортировки (чтобы убить время), которые интенсивно используют функции repeat / until и break. Меня поразило, что функции рекурсивного хвостового вызова могут достигать точно такого же результата, лишь с небольшим ухудшением читабельности. Итак, я выбросил «изменяемый bDone» и «пока не bDone» и попытался написать код без этих императивных конструкций. Ниже приведены только части цикла и показано, как писать код в стиле repeat / until, do / while, while / do, break / continue и test-in-the-middle с использованием хвостовых вызовов. Кажется, что все они работают с точно такой же скоростью, что и традиционный оператор while в F #, но ваш пробег может отличаться (некоторые платформы могут не реализовывать хвостовой вызов должным образом и, следовательно, могут вызывать сбой, пока они не будут исправлены). В конце приводится (плохой) алгоритм сортировки, написанный в обоих стилях для сравнения.

Давайте начнем с цикла «do / while», написанного в традиционном императивном стиле F #, а затем рассмотрим функциональные варианты, которые обеспечивают одинаковый тип of цикла, а также различные семантики, такие как while / do, repeat / until, test в середине, и даже break / continue (без монад .. ммм, рабочие процессы!)

#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000

let imperDoWhile() =
    let mutable x = 0
    let mutable bDone = false
    while not bDone do
        f()
        x <- x + 1
        if x >= N then bDone <- true

Хорошо, это достаточно просто. Имейте в виду, что f () всегда вызывается хотя бы один раз (do / while).

Это тот же код, но в функциональном стиле. Обратите внимание, что здесь нам не нужно объявлять изменяемый.

let funDoWhile() =
    let rec loop x =
        f()             (*Do*)
        if x < N then   (*While*)
            loop (x+1)
    loop 0

Мы можем преобразовать это в традиционный do / while, поместив вызов функции внутри блока if.

let funWhileDo() =
    let rec loop x =
        if x < N then   (*While*)
            f()         (*Do*)
            loop (x+1)
    loop 0

Как насчет повторения блока до тех пор, пока какое-то условие не станет истинным ( повтор / до)? Достаточно просто ...

let funRepeatUntil() =
    let rec loop x =
        f()                 (*Repeat*)
        if x >= N then ()   (*Until*)
        else loop (x+1)
    loop 0

Что это было насчет разрыва без монад? Что ж, просто введите условное выражение, возвращающее «единицу», например:

let funBreak() =
    let rec loop() =
        let x = g()
        if x > N then ()    (*break*)
        else
            f()
            loop()
    loop()

Как насчет продолжения? Что ж, это просто еще один вызов цикла! Во-первых, с помощью синтаксического костыля:

let funBreakContinue() =
    let break' () = ()
    let rec continue' () =
        let x = g()
        if   x > N then break'()
        elif x % 2 = 0 then
            f(); f(); f();
            continue'()
        else
            f()
            continue'()
    continue'()

А затем снова без (уродливого) синтаксического костыля:

let funBreakContinue'() =
    let rec loop () =
        let x = g()
        if   x > N then ()
        elif x % 2 = 0 then
            f(); f(); f();
            loop()
        else
            f()
            loop ()
    loop()

Легко, как пирог!

Одним из хороших результатов этих форм цикла является то, что он упрощает обнаружение и реализацию состояний в ваши петли. Например, пузырьковая сортировка постоянно проходит по всему массиву, замена значений, которые неуместны, когда он их находит. Он отслеживает, произвел ли проход по массиву какие-либо обмены. В противном случае каждое значение должно быть в нужном месте, чтобы сортировка могла завершиться. В качестве оптимизации при каждом проходе через массив последнее значение в массиве оказывается отсортированным в нужное место. Таким образом, цикл может быть сокращен на единицу каждый раз. Большинство алгоритмов проверяют наличие свопа и обновляют флаг «bModified» каждый раз, когда он есть. Однако после того, как первый обмен выполнен, в этом назначении нет необходимости; оно уже установлено в true!

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

let inline sort2 f i j (a:'a array) =
    let i' = a.[ i ]
    let j' = a.[ j ]
    if f i' j' > 0 then
        a.[ i ] <- j'
        a.[ j ] <- i'

let bubble f (xs:'a array) =
    if xs.Length = 0
    then ()

    let rec modified i endix =
        if i = endix then
            unmodified 0 (endix-1)
        else
            let j = i+1
            sort2 f i j xs
            modified j endix
    and unmodified i endix =
        if i = endix then
            ()
        else
            let j = i+1
            let i' = xs.[ i ]
            let j' = xs.[ j ]
            if f i' j' > 0 then
                xs.[ i ] <- j'
                xs.[ j ] <- i'
                modified j endix
            else
                unmodified j endix
    in unmodified 0 (xs.Length-1)

let bubble_imperitive f (xs:'a array) =
    let mutable bModified = true
    let mutable endix = xs.Length - 1
    while bModified do
        bModified <- false
        endix <- endix - 1
        for i in 0..endix do
            let j = i+1
            let i' = xs.[ i ]
            let j' = xs.[ j ]
            if f i' j' > 0 then
                xs.[ i ] <- j'
                xs.[ j ] <- i'
                bModified <- true
        done
    done