Lista fragmentów kodu funkcjonalnego dla programistów proceduralnych?

Question

Czasami wciąż utknąłem próbując przetłumaczyć kod proceduralny na funkcjonalny kod.

Czy istnieje lista funkcjonalnych idiomów/fragmentów, które są odwzorowane na idiomy proceduralne/fragmenty kodu?

Edit

Ponieważ nie wydaje się być scentralizowana strona z tych fragmentów, ja obracając to w wiki społeczności. Wklej tutaj wszelkie formalne -> opisy funkcjonalne.

Answer 1

(Zmieniano z this post na fshub)

Po raz pierwszy pojechałem do sięgnięcia po przerwie/kontynuować w OCaml/F #, to wyrzucił mnie za (nieskończony), że tak powiem, ponieważ nic takiego nie istnieje! W OCaml można używać wyjątków, aby zerwać z pętli, ponieważ są one tanie, ale w F # (w.NET) narzut jest dość wysoki i nie jest przydatny do "normalnej" kontroli przepływu.

Pojawiło się podczas gry z algorytmami sortowania po chwili (aby zabić trochę czasu), które intensywnie wykorzystują powtarzanie/do i przerwanie. Uderzyło mnie to, że rekursywne funkcje wywołania końcowego mogą osiągnąć dokładnie taki sam wynik, z niewielkim tylko dingiem do czytelności. Wyrzuciłem więc "mutable bDone" i "while not bDone" i próbowałem pisać kod bez tych imperatywnych konstrukcji. Poniższe fragmenty wypakowują tylko części z zapętleniami i pokazują, jak pisać powtórzenia/do, do/while, while/do, break/continue, i testuj w środku kodu stylu za pomocą tailcalls. Wszystkie te wydają się działać z taką samą prędkością, jak tradycyjne F # 'while', ale twój przebieg może się różnić (niektóre platformy mogą nieprawidłowo implementować tailcall i dlatego mogą ustawiać błędy, 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 F #, następnie spójrzmy na warianty funkcjonalne, które zapewniają zarówno ten sam typ pętli, jak i różne semantyki, takie jak while/do, repeat/until, testuj w środku, a nawet przerwij/kontynuuj (bez monad .. um, workflows!).

#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 

Ok, to dość łatwe. Pamiętaj, że f() jest zawsze wywoływane co najmniej raz (do/while).

Oto ten sam kod, ale w stylu funkcjonalnym. Zwróć uwagę, że nie musimy tutaj zadeklarować zmiennej.

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

Możemy obrócić to do tradycyjnego do/while poprzez umieszczenie wywołania funkcji wewnątrz bloku if.

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

Co powiesz na powtarzanie bloku, aż spełniony zostanie warunek (powtórzenie/zamknięcie)? Wystarczająco łatwe ...

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

Co to było o przerwie bez monady? Cóż, wystarczy wprowadzić wyrażenie warunkowe, które zwraca "jednostkę", jak w:

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

Co powiesz na kontynuację? Cóż, to kolejne połączenie do pętli! Po pierwsze, o kuli 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'() 

a następnie ponownie bez kuli (brzydki) Składnia:

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

bułka z masłem!

Jednym z ładnych rezultatów tych form pętli jest to, że ułatwia wykrywanie i wdrażanie stanów w pętlach. Na przykład sortowanie bąbelkowe nieustannie wykonuje pętle w całej tablicy, zamieniając wartości, które są nie na miejscu, gdy je znajdzie. Śledzi, czy przejście przez tablicę powoduje jakiekolwiek wymiany. Jeśli nie, to każda wartość musi być we właściwym miejscu, aby sortowanie mogło zakończyć się. Jako optymalizacja, przy każdym przejściu przez tablicę ostatnia wartość w tablicy kończy się w odpowiednim miejscu. Tak więc pętlę można skrócić o jeden za każdym razem. Większość algorytmów sprawdza zamiany i aktualizuje flagę "bModified" za każdym razem, gdy jest taka. Jednak po zakończeniu pierwszej wymiany nie ma potrzeby wykonywania tego przypisania; jest już ustawione na true!

Oto kod F #, który implementuje sortowanie bąbelkowe (tak, sortowanie bąbelkowe jest okropnym algorytmem, skały quicksort). 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 w przypadku małych tablic i tylko o jeden procent lub dwa wolniejsze w przypadku dużych. (Stworzony 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 

Answer 2

Och, teraz jest to sprytne pytanie. Oto niektóre, code snips in python lub coś Cloe:

• pętli można zastąpić iteratorów

  stripped_list = [line.strip() for line in line_list]

• pętli można zastąpić zastosować lub mapy lub filtrować

  mapa (górna, ["zdanie", "fragment"])[ 'zdanie' 'FRAGMENTU']

• zagnieżdżonej pętli z kompozycją funkcji

• ogon rekursji zamiast pętli

• generator wyrażenia w miejscu dla pętle

  sum(x*x for x in range(10))

Answer 3

Old praca domowa pytanie:

Funkcja

(define f-imperative (y) (x) ; x is a local variable 
    (begin 
    (set x e) 
    (while (p x y) 
     (set x (g x y))) 
    (h x y))) 

jest w typowym stylu bezwzględnej, wraz z cesją i pętli. Napisz równoważną funkcję f-funkcyjną, która nie używa funkcji rozkazujących (sekwencjonowanie), while (goto) i ustaw (przypisanie). Możesz używać tylu "funkcji pomocniczych", ile chcesz, o ile są zdefiniowane za pomocą let lub letrec, a nie na najwyższym poziomie.

Jedno rozwiązanie:

; The idea is simple: 
; Use parameter passing for binding the values 
; of the variables and recursion instead of iteration. 
; 
; For those who like theory this is the main argument for proving 
; that recursive functions (LISP, lambda calculus) have the same 
; computational power as any imperative programming language. 

(define f-functional (y) 
    (letrec (
    (f-helper (lambda (x y) 
        (if (p x y) 
        (f-helper (g x y) y) 
        (h x y))))) 
    (f-helper e y))) 

; Notice that y in f-helper is invariant. Therefore, we can rewrite 
; f-helper without y as follows. 

(define f-functional (y) 
    (letrec (
    (f-helper (lambda (x) 
        (if (p x y) 
        (f-helper (g x y)) 
        (h x y))))) 
    (f-helper e))) 

; This is not the only solution, though I think it is one of the 
; nicer ones. 

Answer 4

Fałd jest bardzo interesującą funkcją, która jest centralna w wielu funkcjonalnych algorytmach. Powiedzmy, że chcemy dodać wszystkie elementy listy. W kodzie proceduralnym generalnie tworzysz zmienną akumulującą i ustawiasz ją na 0, a następnie iterujesz listę i inkrementujesz akumulator przez element.

W SML, należy wykonać te same czynności w sposób funkcjonalny przy użyciu krotnie:

List.fold_left (+) 0 [1; 2; 3];; 
- : int = 6 

Korzystanie krotnie, można na przykład policzyć liczbę słów w liście i złączyć je w tym samym czasie:

List.fold_left (fun (count, concat) e -> (count + 1, concat^e)) (0, "") ["a"; "b"; "c"];; 
- : int * string = (3, "abc") 

Innym przydatnym wykorzystaniem złożenia jest skopiowanie wektora do zestawu. Ponieważ zestawy w Ocaml są niezmienne, musisz stworzyć dla każdego elementu listy nowy zestaw, który zawiera poprzedni zestaw oraz nowy element.

module Int = struct type t = int let compare = compare end;; 
module IntSet = Set.Make(Int);; 

let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];; 
val s : IntSet.t = <abstr> 

IntSet.elements s;; 
- : IntSet.elt list = [1; 2; 3] 

Tutaj nasz początkowy obiekt jest zbiorem pustym, a przy każdym połączeniu, nowy zestaw jest tworzony na podstawie poprzedniego zestawu i aktualnej pozycji przy użyciu IntSet.add.

Wciśnij jeden raz rekursywnie siebie, aby dowiedzieć się, jak to zrobić pod maską, a następnie użyj wbudowanej wersji wszędzie. Nawet w C++, z std::accumulate!

Answer 5

Projekt PLEAC ma dokładnie taki cel, jak jest to możliwe - zaimplementuj wszystkie przykłady w książce kucharskiej perl w innych językach. Oto linki do wersji ocaml (która jest jednym z trzech 100% kompletnych) http://pleac.sourceforge.net/pleac_ocaml/index.html