W jaki sposób zapamiętuje się tę funkcję Fibonacciego?

Jaki mechanizm zapamiętuje tę funkcję Fibonacciego?

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

A z drugiej strony, dlaczego ta wersja nie jest?

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

Mechanizm oceny w Haskell jest konieczny : gdy potrzebna jest wartość, jest ona obliczana i utrzymywana w stanie gotowości na wypadek ponownego zażądania. Jeśli zdefiniujemy jakąś listę, xs=[0..]a później poprosimy o jej setny element, xs!!99to setna pozycja na liście zostanie „uzupełniona”, trzymając 99teraz numer , gotowy do następnego dostępu.

To właśnie wykorzystuje ta sztuczka, „przeglądanie listy”. W normalnej podwójnie rekurencyjnej definicji Fibonacciego, fib n = fib (n-1) + fib (n-2)sama funkcja jest wywoływana dwukrotnie od góry, powodując wykładniczą eksplozję. Ale dzięki tej sztuczce stworzyliśmy listę tymczasowych wyników i przejrzeliśmy „listę”:

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

Sztuczka polega na tym, aby spowodować utworzenie tej listy i sprawić, by ta lista nie znikała (poprzez czyszczenie pamięci) między wywołaniami funkcji fib. Najłatwiejszym sposobem osiągnięcia tego jest nazwanie tej listy. „Jeśli go nazwiesz, pozostanie”.

Twoja pierwsza wersja definiuje stałą monomorficzną, a druga definiuje funkcję polimorficzną. Funkcja polimorficzna nie może używać tej samej wewnętrznej listy dla różnych typów, które może potrzebować do obsługi, więc nie ma udostępniania , czyli nie ma zapamiętywania.

W pierwszej wersji kompilator jest dla nas hojny , map fib' [0..]usuwając to stałe podwyrażenie ( ) i czyniąc z niego oddzielną jednostkę, którą można udostępniać, ale nie ma takiego obowiązku. ^{w rzeczywistości są przypadki, w których nie chcemy, aby robiła to za nas automatycznie.}

( edytuj :) Rozważ te ponowne zapisy:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

Więc prawdziwa historia wydaje się dotyczyć definicji zakresu zagnieżdżonego. Nie ma zakresu zewnętrznego z pierwszą definicją, a trzeci jest ostrożny, aby nie wywołać zakresu zewnętrznego fib3, ale ten sam poziom f.

Każde nowe wywołanie fib2wydaje się tworzyć na nowo swoje zagnieżdżone definicje, ponieważ każda z nich może (w teorii) być zdefiniowana inaczej w zależności od wartości n(dzięki Vitusowi i Tichonowi za zwrócenie na to uwagi). Z pierwszą definicją nie nmożna polegać, az trzecią jest zależność, ale każde oddzielne wywołanie fib3wywołań, do fktórych należy uważać, aby wywołać definicje tylko z zakresu tego samego poziomu, wewnętrznego dla tego konkretnego wywołania fib3, więc to samo xsdostaje się ponownie wykorzystane (tj. udostępnione) dla tego wywołania fib3.

Ale nic nie stoi na przeszkodzie, aby kompilator rozpoznał, że wewnętrzne definicje w którejkolwiek z powyższych wersji są w rzeczywistości niezależne od zewnętrznego npowiązania, aby wykonać podniesienie lambda , co skutkuje pełną zapamiętaniem (z wyjątkiem definicji polimorficznych). W rzeczywistości dokładnie to dzieje się ze wszystkimi trzema wersjami, gdy są zadeklarowane z typami monomorficznymi i skompilowane z flagą -O2. W przypadku deklaracji typu polimorficznego fib3wykazuje udostępnianie lokalne i fib2brak udostępniania.

Ostatecznie, w zależności od kompilatora i użytych optymalizacji kompilatora oraz tego, jak go testujesz (ładowanie plików w GHCI, skompilowanych lub nie, z -O2 lub nie, lub samodzielnie) i czy otrzyma typ monomorficzny czy polimorficzny, zachowanie może całkowicie zmienić - czy wykazuje udostępnianie lokalne (na każde połączenie) (tj. liniowy czas każdego połączenia), zapamiętywanie (tj. liniowy czas pierwszego połączenia i zerowy czas podczas kolejnych połączeń z tym samym lub mniejszym argumentem), czy też brak udostępniania ( wykładniczy czas).

Krótka odpowiedź brzmi: to kwestia kompilatora. :)

Nie jestem do końca pewien, ale oto zgadywanie:

Kompilator zakłada, że fib nmoże to być inne na innym ni dlatego za każdym razem musiałby ponownie obliczyć listę. W końcu bity w whereinstrukcji mogą zależeć n. Oznacza to, że w tym przypadku cała lista liczb jest zasadniczo funkcją n.

Wersja bez n może utworzyć listę raz i zawinąć ją w funkcję. Lista nie może zależeć od wartości nprzekazanej i jest to łatwe do zweryfikowania. Lista jest stałą, która jest następnie indeksowana do. Jest to oczywiście stała, która jest leniwie oceniana, więc program nie próbuje od razu uzyskać całej (nieskończonej) listy. Ponieważ jest to stała, może być współdzielona przez wywołania funkcji.

W ogóle jest zapamiętywany, ponieważ wywołanie rekurencyjne musi po prostu wyszukać wartość na liście. Ponieważ fibwersja tworzy listę raz leniwie, po prostu oblicza wystarczająco dużo, aby uzyskać odpowiedź bez wykonywania zbędnych obliczeń. Tutaj „leniwy” oznacza, że ​​każdy wpis na liście jest złem (nieocenionym wyrażeniem). Kiedy należy ocenić thunk, staje się wartością, więc dostęp do niej następnym razem nie bez powtarzania obliczeń. Ponieważ listę można współużytkować między połączeniami, wszystkie poprzednie wpisy są już obliczane do czasu, gdy potrzebujesz następnego.

Zasadniczo jest to sprytna i tania forma dynamicznego programowania oparta na leniwej semantyce GHC. Myślę standardowe tylko określa, że musi być non-surowe , więc kompilator zgodny potencjalnie mogłyby skompilować ten kod, aby nie memoize. Jednak w praktyce każdy rozsądny kompilator będzie leniwy.

Aby uzyskać więcej informacji o tym, dlaczego drugi przypadek w ogóle działa, przeczytaj Zrozumienie rekurencyjnie zdefiniowanej listy (fibs w kategoriach zipWith) .

Po pierwsze, z ghc-7.4.2, skompilowanym -O2, wersja niezapamiętana nie jest taka zła, wewnętrzna lista liczb Fibonacciego jest nadal zapamiętywana dla każdego najwyższego poziomu wywołania funkcji. Ale nie jest i nie można tego w uzasadniony sposób zapamiętać w ramach różnych wezwań na najwyższym szczeblu. Jednak w przypadku drugiej wersji lista jest wspólna dla wszystkich połączeń.

Wynika to z ograniczenia monomorfizmu.

Pierwsza jest związana prostym wiązaniem wzorca (tylko nazwa, bez argumentów), dlatego przez ograniczenie monomorfizmu musi otrzymać typ monomorficzny. Wywnioskowany typ to

fib :: (Num n) => Int -> n

i takie ograniczenie zostaje ustawione domyślnie (w przypadku braku domyślnej deklaracji mówiącej inaczej) na Integer, ustalając typ jako

fib :: Int -> Integer

Zatem jest tylko jedna lista (typu [Integer]) do zapamiętania.

Druga jest zdefiniowana za pomocą argumentu funkcji, dlatego pozostaje polimorficzna, a jeśli listy wewnętrzne byłyby zapamiętywane w wywołaniach, należałoby zapamiętać jedną listę dla każdego typu w Num. To nie jest praktyczne.

Skompiluj obie wersje z wyłączonym ograniczeniem monomorfizmu lub z identycznymi sygnaturami typu i obie zachowują się dokładnie tak samo. (Nie było to prawdą w przypadku starszych wersji kompilatora, nie wiem, która wersja to zrobiła).

Nie potrzebujesz funkcji memoize dla Haskella. Tylko empiryczny język programowania potrzebuje takich funkcji. Jednak Haskel jest funkcjonalny i ...

Oto przykład bardzo szybkiego algorytmu Fibonacciego:

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith to funkcja ze standardowego Prelude:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

Test:

print $ take 100 fib

Wynik:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

Upłynął czas: 0,00018s