Co oznacza "wypłynięcie"?

Question

Na Haskell wiki I read that this:

fib = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in (map fib' [0 ..] !!) 

jest bardziej wydajny niż to:

fib x = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in map fib' [0 ..] !! x 

Bo „W drugim przypadku fib” jest (re) zdefiniowanej dla każdego argumentu x, zatem nie może wypłynąć. "

Nie rozumiem, co to oznacza.

1. Co oznacza "wypłynięcie"? Jak to jest optymalizacja?
2. Dlaczego ponownie zdefiniowano fib' dla każdej inwokacji fib?
3. Czy to jest rozszerzenie eta, czy nie?

Answer 1

To nie jest bardzo dobre wytłumaczenie.

"wypłynął" oznacza po prostu, że:

\x -> let y = ... in z 

jeśli ... nie wspomina x to może być wypłynął z lambda:

let y = ... in \x -> z 

co oznacza, że zostanie obliczone tylko raz, , co może zaoszczędzić dużo czasu, jeśli koszt jest wysoki: .... GHC jest jednak konserwatywne, jeśli chodzi o takie optymalizacje, ponieważ mogą one wprowadzić kosmiczne wycieki. (Chociaż to robi zrobić dla drugiej definicji, jeśli podasz mu podpis typu, jak Daniel Fischer wskazuje w swojej odpowiedzi.)

Nie chodzi jednak o automatyczną optymalizację. Pierwszy fragment kodu definiuje fib' poza lambdą, podczas gdy drugi definiuje go wewnątrz (lambda jest niejawna w fib x = ..., co jest równoważne fib = \x -> ...), o czym mówi cytat.

Nawet to nie ma znaczenia; Istotne jest to, że w pierwszym fragmencie, map fib' [0 ..] występuje poza lambdą, a więc jego wynik jest dzielony pomiędzy wszystkie aplikacje lambda (w tym kodzie "lambda" powstaje z częściowej aplikacji (!!)). W tym drugim przypadku jest on wewnątrz lambda, a więc prawdopodobnie będzie ponownie obliczony dla każdej aplikacji fib.

Rezultat końcowy jest taki, że poprzednia implementacja buforuje wartości i jest o wiele bardziej wydajna niż ta druga. Zauważ, że wydajność pierwszego fragmentu jest zależna od faktu, że fib' nie podlega bezpośredniemu nawrotowi, ale zamiast tego przez fib, a co za tym idzie, zyskuje dzięki memoizacji.

Jest to związane z rozszerzeniem eta; ten drugi fragment jest rozwinięciem eta pierwszego. Ale oświadczenie, które zacytowałeś, nie wyjaśnia w ogóle, co się dzieje.

Należy zauważyć, że jest to zachowanie specyficzne dla implementacji, a nie część semantyki Haskella. Jednak wszystkie rozsądne implementacje będą zachowywać się w ten sposób.

Answer 2

ehird „s odpowiedź wyjaśnia rzeczy bardzo dobrze, jednak istnieje jeden punkt

Końcowym rezultatem jest to, że były realizacja buforuje wartości i tak jest o wiele bardziej wydajny niż ten ostatni.

czasami jest źle.

Jeśli skompilować moduł zawierający zarówno definicję z optymalizacji (sprawdziłem tylko -O2, nie -O1 i oczywiście tylko GHC), istnieje kilka przypadków do rozważenia:

1. pierwsza definicja bez typu podpis
2. druga definicja z typem podpisu fib :: Int -> Integer
3. pierwsza definicja z polimorficznych typu fib :: Num a => Int -> a
4. druga definicja typu bez podpisu
5. druga definicja z typem podpisu fib :: Num a => Int -> a

W przypadku 1, ograniczenie monomorfizm produkuje typ fib :: Int -> Integer a lista map fib' [0 .. ] jest wspólna dla wszystkich wywołań fib. Oznacza to, że jeśli kiedykolwiek zapytasz o numer fib (10^6), masz listę pierwszych milionów (+1) liczb Fibonacciego w pamięci i będzie ona zbierana tylko wtedy, gdy śmieciarz może stwierdzić, że nie jest już używany. Często jest to przeciek pamięci.

W przypadku 2, wynik (ING rdzeń) jest praktycznie identyczna Przypadek 1.

W przypadku 4, ta lista nie jest wspólna dla różnych wywołań najwyższego poziomu fib (oczywiście, wynik może ma wiele typów, więc byłoby wiele list do udostępnienia), ale jest tworzona raz na wywołanie najwyższego poziomu i jest ponownie używana dla wywołań z fib', więc obliczanie fib n wymaga dodania O (n) i O (n^2) Lista. Nie aż tak źle. Lista jest zbierana, gdy obliczenia są zakończone, więc nie ma wycieku przestrzeni.

Przypadek 3 jest praktycznie identyczna do 4.

Przypadek 5 jest jednak gorzej niż naiwnego rekursji. Ponieważ jest to wyraźnie polimorficzne, a lista jest powiązana wewnątrz lambda, nie można ponownie użyć listy dla wywołań rekursywnych, każde wywołanie rekursywne tworzy nową listę ...