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

114

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)                    
bjornars
źródło
13
Nieco niezwiązane, fib 0nie kończy się: prawdopodobnie chcesz, aby przypadki bazowe fib'były fib' 0 = 0i fib' 1 = 1.
huon
1
Zwróć uwagę, że pierwsza wersja mogłaby być bardziej zwięzła: fibs = 1:1:zipWith (+) fibs (tail fibs)i fib = (fibs !!).
Bastian

Odpowiedzi:

95

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. :)

Will Ness
źródło
4
Żeby naprawić mały szczegół: druga wersja nie ma żadnego udostępniania, głównie dlatego, że funkcja lokalna fib'jest przedefiniowana dla każdego, na zatem fib'w fib 1fib'in fib 2, co również oznacza, że ​​listy są różne. Nawet jeśli naprawisz typ jako monomorficzny, nadal będzie wykazywał takie zachowanie.
Vitus,
1
whereklauzule wprowadzają udostępnianie podobnie jak letwyrażenia, ale mają tendencję do ukrywania problemów, takich jak ten. Przepisując to nieco dokładniej, otrzymujesz to: hpaste.org/71406
Vitus,
1
Kolejna interesująca kwestia dotycząca twojego przepisywania: jeśli nadasz im typ monomorficzny (tj. Int -> Integer), To fib2działa w czasie wykładniczym fib1i fib3oba działają w czasie liniowym, ale fib1są również zapamiętywane - ponownie, ponieważ dla fib3lokalnych definicji są przedefiniowane dla każdego n.
Vitus,
1
@misterbee Ale rzeczywiście byłoby miło mieć jakieś zapewnienie od kompilatora; jakiś rodzaj kontroli nad miejscem przebywania w pamięci określonej jednostki. Czasami chcemy się dzielić, czasami chcemy temu zapobiec. Wyobrażam sobie / mam nadzieję, że to będzie możliwe ...
Will Ness
1
@ElizaBrandt Chodziło mi o to, że czasami chcemy przeliczyć coś ciężkiego, aby nie zostało to dla nas zachowane w pamięci - tj. Koszt ponownego obliczenia jest niższy niż koszt ogromnego zatrzymania pamięci. jednym z przykładów jest tworzenie zestawów PowerSet: pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]chcemy, pwr xsaby były obliczane niezależnie, dwukrotnie, aby można było zbierać śmieci w locie, gdy są produkowane i konsumowane.
Will Ness,
23

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

Tikhon Jelvis
źródło
czy miałeś na myśli, że „ fib' nmoże być inny na innym n”?
Will Ness
Myślę, że nie było to zbyt jasne: miałem na myśli to, że wszystko w środku fib, w tym fib', może być różne na każdym innym n. Myślę, że oryginalny przykład jest trochę zagmatwany, ponieważ fib'zależy również od własnego, nktóry rzuca cień na drugi n.
Tikhon Jelvis,
20

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

Daniel Fischer
źródło
Dlaczego zapamiętanie listy dla każdego typu jest niepraktyczne? W zasadzie, czy GHC może utworzyć słownik (podobnie jak w przypadku wywoływania funkcji ograniczonych przez klasę typu), aby zawierał częściowo obliczone listy dla każdego typu Num napotkanego w czasie wykonywania?
misterbee
1
@misterbee W zasadzie tak, ale jeśli program wywołuje fib 1000000wiele typów, zjada to mnóstwo pamięci. Aby tego uniknąć, potrzebna byłaby heurystyka, która wyświetla listę wyrzuconą z pamięci podręcznej, gdy stanie się ona zbyt duża. Taka strategia zapamiętywania prawdopodobnie miałaby również zastosowanie do innych funkcji lub wartości, więc kompilator musiałby radzić sobie z potencjalnie dużą liczbą rzeczy do zapamiętania dla potencjalnie wielu typów. Myślę, że możliwe byłoby zaimplementowanie (częściowej) memizowania polimorficznego z dość dobrą heurystyką, ale wątpię, czy byłoby to opłacalne.
Daniel Fischer,
5

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

Валерий Кобзарь
źródło
To rozwiązanie jest świetne!
Larry