Lista urywków kodu funkcyjnego dla programistów proceduralnych? [zamknięte]

(Edited from this post on fshub )

Pierwszy raz, kiedy poszedłem sięgnąć po break / continue w OCaml / F#, rzuciło mnie to na (nieskończoną) pętlę, że tak powiem, bo czegoś takiego nie ma! W OCaml można użyć WYJĄTKÓW do przerwania pętli, ponieważ są one bardzo tanie, ale w F #(W.NET) narzut jest dość wysoki i nie jest przydatny do "normalnej" kontroli przepływu.

To pojawiło się podczas zabawy z algorytmami sortowania jakiś czas temu (aby zabić trochę czasu), które w dużym stopniu wykorzystują powtarzanie / aż I łamanie. Dotarło do mnie, że rekurencyjne funkcje wywołania ogonowego mogą osiągnąć dokładnie ten sam wynik, tylko z niewielkim naciśnięciem na czytelność. Wyrzuciłem więc 'mutable bDone' I 'while not bDone' i próbowałem napisać kod bez tych imperatywnych konstrukcji. Poniżej przedstawiamy tylko zapętlone części i pokazujemy jak napisać kod repeat/until, do/while, while/do, break / continue i test-in-the-middle używając tailcalls. Te wszystkie wydają się biegać w dokładnie taka sama prędkość jak tradycyjna Instrukcja F # 'while' , ale przebieg może się różnić (niektóre platformy mogą nie poprawnie zaimplementować tailcall i w związku z tym mogą powodować błędy w stosie, dopóki nie zostaną poprawione). Na końcu jest (zły) algorytm sortowania napisany w obu stylach, dla porównania.

Zacznijmy od pętli 'do / while', napisanej w tradycyjnym stylu imperatywnym F#, a następnie przyjrzyjmy się wariacjom funkcjonalnym, które zapewniają zarówno ten sam typ pętli, jak i różne semantyki, takie jak while/do, powtarzaj / aż, Testuj w środku, a nawet przerywaj / kontynuuj (bez monad.. przepływ pracy!).

#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

Oto ten sam kod, ale w funkcjonalnym stylu. Zauważ, że nie musimy tutaj deklarować mutacji.

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

Możemy zamienić to na tradycyjne do / while, umieszczając wywołanie funkcji wewnątrz bloku if.

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

Może powtórzymy blok, aż jakiś warunek będzie true (repeat/until)? Dość łatwo...

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

O co chodziło z przerwą bez monad? Cóż, po prostu wprowadź wyrażenie warunkowe, które zwraca 'unit', jak w:

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

Może dalej? To tylko kolejne wezwanie do pętli! Po pierwsze, ze składnią:

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'()

I znowu bez (brzydkiej) składni:

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()

Łatwe jak ciasto!

Jednym z miłych rezultatów tych formularzy pętli jest to, że ułatwia dostrzeżenie i wdrożenie stanów w Twoim pętle. Na przykład sortowanie bąbelków stale pętli na całej tablicy, zamieniając wartości, które są nie na miejscu, gdy je znajduje. Śledzi, czy przejście nad tablicą spowodowało jakiekolwiek wymiany. Jeśli nie, to każda wartość musi być we właściwym miejscu, aby sortowanie mogło się zakończyć. Jako Optymalizacja, przy każdym przejściu przez tablicę, ostatnia wartość w tablicy kończy się posortowana we właściwe miejsce. Tak więc pętlę można skrócić o jeden za każdym razem. Większość algorytmów sprawdza zamianę i Aktualizuj flagę" bModified " za każdym razem, gdy taka istnieje. Jednak, gdy pierwsza Zamiana zostanie wykonana, nie ma potrzeby takiego przypisania; jest już ustawione na true!

Oto Kod F#, który implementuje sortowanie bąbelków (tak, sortowanie bąbelków jest strasznym algorytmem; quicksort rządzi). Na końcu jest imperatywna implementacja, która nie zmienia stanu; aktualizuje flagę bModified dla każdej wymiany. Co ciekawe, imperatywne rozwiązanie jest szybsze na małych tablicach i tylko jeden lub dwa wolniejsze na Duże. (Choć na dobry przykład).

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