Programowanie funkcyjne-duży nacisk na rekurencję, dlaczego?

Czyste programowanie funkcjonalne oznacza programowanie bez skutków ubocznych. Co oznacza, że jeśli napiszesz pętlę na przykład, ciało Twojej pętli nie może wywołać skutków ubocznych. Tak więc, jeśli chcesz, aby Twoja pętla coś zrobiła, musi ponownie użyć wyniku poprzedniej iteracji i wytworzyć coś do następnej iteracji. Tak więc ciało pętli jest funkcją, która przyjmuje jako parametr wynik poprzedniego wykonania i wywołuje się do następnej iteracji z własnym wynikiem. To nie ma ogromna przewaga nad bezpośrednim zapisem funkcji rekurencyjnej dla pętli.

Program, który nie robi czegoś trywialnego, będzie musiał w pewnym momencie coś zmienić. Dla programowania funkcyjnego oznacza to, że program musi używać funkcji rekurencyjnych.

Funkcja, która wywołuje wymóg że robisz rzeczy rekurencyjnie jest zmiennymi niezmiennymi.

Rozważmy prostą funkcję do obliczania sumy listy (w pseudokodzie):

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

Teraz element w każdej iteracji listy jest inna, ale możemy to przepisać, aby użyć funkcji foreach z argumentem lambda, aby pozbyć się tego problemu:

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

Mimo to wartość zmiennej {[6] } musi być zmieniana w każdym przebiegu lambda. To jest nielegalne w języku z niezmiennymi zmiennymi, więc musisz go przepisać w sposób, który nie zmutuje stanu:

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

Teraz, ta implementacja będzie wymagała pchania i wyskakiwania ze stosu wywołań, a program, w którym wszystkie małe operacje by to zrobiły, nie będzie działał zbyt szybko. Dlatego przepisujemy go jako rekurencyjny, więc kompilator może wykonać optymalizację wywołania tail:

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

Oczywiście, jeśli chcesz zapętlić w nieskończoność, absolutnie potrzebujesz rekurencyjnego ogona zadzwoń, albo będzie przepełnienie stosu.

Adnotacja @tailrec w Scali Jest narzędziem do analizy, które funkcje są rekurencyjne. Twierdzisz ,że "ta funkcja jest rekurencyjna", a kompilator może Ci powiedzieć, jeśli się mylisz. Jest to szczególnie ważne w Scali w porównaniu z innymi językami funkcyjnymi, ponieważ maszyna, na której działa, JVM, nie obsługuje dobrze optymalizacji wywołań ogonowych, więc nie jest możliwe uzyskanie optymalizacji wywołań ogonowych w Scali okoliczności, które można uzyskać w innych językach funkcyjnych.

TL; DR: rekurencja jest używana do obsługi indukcyjnie zdefiniowanych danych, które są wszechobecne.

Rekurencja jest naturalna, gdy operujemy na wyższych poziomach abstrakcji. Programowanie funkcyjne to nie tylko kodowanie za pomocą funkcji; chodzi o operowanie na wyższych poziomach abstrakcji, gdzie w naturalny sposób używa się funkcji. Używając funkcji, naturalne jest ponowne użycie tej samej funkcji( wywołanie jej ponownie), niezależnie od kontekstu, w którym ma to sens.

Świat budowany jest przez powtarzanie podobnych / tych samych klocków. Jeśli wyciąć kawałek tkaniny na dwie części, masz dwa kawałki tkaniny. Indukcja matematyczna jest sercem matematyki. My, ludzie, liczymy (jak w, 1,2,3...). Dowolna indukcyjnie zdefiniowana rzecz (podobnie, {liczby z 1} są {1 , i liczby z 2} ) jest naturalne, aby obsługiwać / analizować przez funkcję rekurencyjną, zgodnie z tymi samymi przypadkami, w których to coś jest zdefiniowany/skonstruowany.

Rekurencja jest wszędzie. Każda pętla iteracyjna i tak jest rekurencją w ukryciu, ponieważ kiedy ponownie wchodzisz do tej pętli, ponownie wchodzisz do tej samej pętli (tylko z może różnymi zmiennymi pętli). Więc nie chodzi o wymyślanie nowych pojęć o komputerach, chodzi raczej o odkrywanie fundamentów i czynienie z nichjawnych .

Więc rekurencja jest naturalna. Po prostu zapisujemy jakieś przepisy o naszym problemie, niektóre równania obejmujące funkcję, którą definiujemy, które zachowują pewną niezmienność (przy założeniu, że funkcja jest spójnie zdefiniowana), ponownie określając problem w uproszczonych terminach i voila! Mamy rozwiązanie.

Przykład, funkcja do obliczania długości listy (indukcyjnie zdefiniowany rekurencyjny typ danych). Załóżmy, że jest zdefiniowana i zwraca długość listy, nie zaskakując. Jakie prawa musi przestrzegać? Co niezmienne jest zachowane pod jakim uproszczeniem problem?

Najpilniejsze jest rozdzielenie listy na jej element head, a reszta-czyli ogon listy (w zależności od tego, jak lista jest zdefiniowana/skonstruowana). Prawo jest,

length (x:xs) = 1 + length xs

length [] = 0

Jak więc napisać taką funkcję?... Czekaj... Już to napisaliśmy! (W Haskell, jeśli zastanawiasz się, gdzie aplikacja funkcji jest wyrażona przez zestawienie, nawiasy są używane tylko do grupowania i (x:xs) jest listą z {[6] } jej pierwszym elementem, a xs resztą).

Jedyne czego potrzebujemy od języka, aby pozwolić na taki styl programowania to to, że ma on TCO (i być może, trochę luksusowo, TRMCO {28]}), więc nie ma wysadzenia stosu i jesteśmy ustawieni.

Kolejną rzeczą jest czystość-niezmienność zmiennych kodu i / lub struktury danych (pola rekordów itp.).

Co to robi, poza uwolnieniem naszych umysłów od konieczności śledzenia tego, co się zmienia, gdy, czy to sprawia, że czas wyraźnie widoczny w naszym kodzie, zamiast ukrywać się w naszych "zmieniających się" zmiennych/danych. Możemy tylko "zmienić" w kodzie imperatywnym wartość zmiennej od teraz - nie możemy zbyt dobrze zmienić jej wartości w przeszłości, prawda?

I tak kończymy z listą zapisanej historii zmian, ze zmianą wyraźnie widoczną w kodzie: zamiast x := x + 2 piszemy let x2 = x1 + 2. Ułatwia to rozumowanie o kodzie.

Aby rozwiązać problem niezmienności w kontekście rekurencji ogonowej z TCO , rozważmy ten rekurencyjny zapis powyższej funkcji length pod paradygmatem argumentu akumulatora:

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     length of 2nd arg

Tutaj TCO oznacza ponowne użycie ramki wywołania, oprócz bezpośredniego skoku, a więc łańcuch wywołań dla length [1,2,3] może być postrzegany jako zmutowanie wpisów ramki wywołań odpowiadających parametrom funkcji:

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

W czystym języku, bez żadnych mutujących wartości prymitywów, jedynym sposobem wyrażenia zmiany jest aby przekazać zaktualizowane wartości jako argumenty do funkcji, która ma być dalej przetwarzana. Jeśli dalsze przetwarzanie jest takie samo jak wcześniej, to naturalnie musimy wywołać tę samą funkcję, przekazując jej zaktualizowane wartości jako argumenty. I to jest rekursja.

I poniżej znajduje się cała historia obliczania długości listy argumentów explicit (i dostępna do ponownego użycia, jeśli zajdzie taka potrzeba):

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

W Haskell jest to różnie znane jako rekurencja strzeżona, czyli corecursion (przynajmniej tak mi się wydaje).

Nie ma nic 'specjalnego' w rekurencji. Jest to powszechne narzędzie w programowaniu i matematyce i nic więcej. Jednak języki funkcjonalne są zazwyczaj minimalistyczne. Wprowadzają wiele wymyślnych pojęć, takich jak dopasowywanie wzorców, system typów, rozumienie list i tak dalej, ale to nic więcej niż cukier składniowy dla bardzo ogólnych i bardzo potężnych, ale prostych i prymitywnych narzędzi. Narzędzia te To: abstrakcja funkcji i aplikacja funkcji. Jest to świadomy wybór, gdyż prostota rdzeń języka znacznie ułatwia rozumowanie. Ułatwia również pisanie kompilatorów. Jedynym sposobem opisania pętli w kategoriach tego narzędzia jest użycie rekurencji, więc programiści mogą myśleć, że programowanie funkcyjne polega na rekurencji. Nie jest, po prostu trzeba naśladować te fantazyjne pętle dla biednych, którzy nie mogą upuścić tego cukru składniowego nad goto stwierdzeniem, a więc jest to jedna z pierwszych rzeczy, w które utknęli.

Kolejny punkt, w którym (może być pośredni) wymagana rekurencja to przetwarzanie rekurencyjnie zdefiniowanych struktur danych. Najczęstszym przykładem jest list ADT. W FP jest to zwykle zdefiniowane tak data List a = Nil | Branch a (List a). Ponieważ definicja ADT tutaj jest rekurencyjna, funkcja przetwarzania dla niego powinna być również rekurencyjna. Ponownie, rekurencja tutaj nie jest i tak specjalny: przetwarzanie takiego ADT w sposób rekurencyjny wygląda naturalnie zarówno w językach imperatywnych jak i funkcyjnych. Cóż, w przypadku list-like ADT imperatyw pętle nadal mogą być przyjęte, ale w przypadku różne struktury przypominające drzewa, których nie mogą.

Nie ma więc nic specjalnego w rekurencji. Jest to po prostu inny rodzaj aplikacji funkcyjnej. Jednak ze względu na ograniczenia nowoczesnych systemów obliczeniowych (wynikające ze źle podjętych decyzji projektowych w języku C, który jest de facto standardowym wieloplatformowym asemblerem) wywołania funkcji nie mogą być zagnieżdżane w nieskończoność, nawet jeśli są wywołaniami ogonowymi. Z tego powodu projektanci funkcjonalnych języków programowania muszą albo ograniczyć dozwolone wywołania ogonowe do rekurencji ogonowej (scala) lub użyć skomplikowanych technik, takich jak trampoling (Stary ghc codegen) lub skompilować bezpośrednio do asm (nowoczesny GHC codegen).

TL;DR: nie ma nic specjalnego w rekurencji W FP, nie więcej niż przynajmniej w IP, jednak rekurencja ogonowa jest jedynym rodzajem wywołań ogonowych dozwolonym w Scali ze względu na ograniczenia JVM.

Unikanie efektów ubocznych jest jednym z filarów programowania funkcyjnego (drugim jest korzystanie z funkcji wyższego rzędu).

Wyobraź sobie, jak możesz wykorzystać imperatywną kontrolę przepływu bez polegania na mutacji. Czy to możliwe?

Oczywiście for (var i = 0; i < 10; i++) ... zależy od mutacji (i++). W rzeczywistości każda konstrukcja pętli warunkowej ma. W while (something) ... something będzie zależeć od jakiegoś zmiennego stanu. Jasne, while (true) ... nie używa mutacji. Ale jeśli kiedykolwiek chcesz z tej pętli będziesz potrzebował if (something) break. Naprawdę, spróbuj pomyśleć o (nieskończonym) mechanizmie zapętlania innym niż rekursja, który nie opiera się na mutacji.

A co z for (var x in someCollection) ...? Teraz zbliżamy się do programowania funkcyjnego. x można traktować jako parametr do ciała pętli. Ponowne użycie nazwy to nie to samo, co ponowne przypisanie wartości. Być może w ciele pętli masz yield return wartości jako wyrażenie w kategoriach x (brak mutacji).

Dokładnie równoważnie, można przenieść ciało pętli {[10] } do ciała funkcji foo (x) ..., a następnie odwzorować ją na {[12] } za pomocą funkcji wyższego rzędu-zastępując konstrukcję pętli czymś w rodzaju Map(foo, someCollection).

Ale w jaki sposób funkcja biblioteki Map jest zaimplementowana bez mutacji? Oczywiście przy użyciu rekurencji! To dla Ciebie. Mniej powszechne staje się samodzielne implementowanie funkcji rekurencyjnych, gdy zaczniesz używać drugiego Pilara funkcji wyższego rzędu, aby zastąpić pętlę konstrukcje.

Dodatkowo, przy optymalizacji wywołania ogonowego definicja rekurencyjna jest równoważna procesowi iteracyjnemu. Możesz również cieszyć się tym wpisem na blogu: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

Istnieją dwie właściwości, które uważam za niezbędne w programowaniu funkcyjnym:

1. Funkcje są członkami pierwszej klasy (tylko istotne, ponieważ aby uczynić je użytecznymi, potrzebna jest druga właściwość)

2. Funkcje są czyste, tzn. funkcja wywołana z tymi samymi argumentami zwraca tę samą wartość.

Teraz, jeśli programujesz w stylu imperatywnym, musisz użyć przypisania.

Rozważmy pętlę for. Posiada indeks i na każdej iteracji indeks ma inną wartość. Można więc zdefiniować funkcję, która zwraca ten indeks. Jeśli wywołasz tę funkcję dwa razy, możesz uzyskać inne wyniki. Tym samym łamiąc zasadę nr 2.

Jeśli złamiesz zasadę nr 2. przekazywanie funkcji (zasada nr 1) staje się czymś niezwykle niebezpiecznym, ponieważ teraz wynik funkcji może zależeć od tego, kiedy i jak często dana funkcja jest wywoływana.

Ostatnim razem, gdy używałem języka funkcyjnego (Clojure), nigdy nie kusiłem się nawet rekursją. Wszystko można było rozpatrywać jako zbiór rzeczy, do których zastosowano funkcję, aby uzyskać produkty częściowe, do których zastosowano inną funkcję, aż do osiągnięcia ostatecznego wyniku.

Rekurencja jest tylko jednym sposobem, A niekoniecznie najczystszym, aby obsłużyć wiele elementów, które zwykle musisz obsłużyć, aby poradzić sobie z dowolnym g

Ze względu na nowych uczniów FP chciałbym dodać swoje 2 cents.As wspomniane w niektórych odpowiedziach, rekurencja jest ich do korzystania z niezmiennych zmiennych, ale dlaczego musimy to zrobić ? to dlatego, że ułatwia uruchamianie programu na wielu rdzeniach równolegle, ale dlaczego tego chcemy ? Nie możemy uruchomić go w jednym rdzeniu i być szczęśliwi, jak zawsze byliśmy ? Nie, ponieważ zawartość do przetworzenia rośnie z dnia na dzień, a cykl zegara procesora nie może być tak znacząco zwiększony, niż dodanie większej liczby rdzeni. Od ostatniej dekady Prędkość zegara została około 2.7 ghz do 3.0 ghz dla komputerów konsumenckich i projektantów układów scalonych mają problemy w montażu coraz więcej tranzystorów w ich.Również FP jest ich od bardzo dawna, ale nie podnieść jak to używane rekurencji i pamięci było bardzo drogie w tych dniach, ale jak prędkości zegara były szybsze rok po roku, więc społeczność postanowiła kontynuować z OOP Edit: było dość szybko, miałem tylko kilka minut