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)
fib 0
nie kończy się: prawdopodobnie chcesz, aby przypadki bazowefib'
byłyfib' 0 = 0
ifib' 1 = 1
.fibs = 1:1:zipWith (+) fibs (tail fibs)
ifib = (fibs !!)
.Odpowiedzi:
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!!99
to setna pozycja na liście zostanie „uzupełniona”, trzymając99
teraz 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ę”: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:
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 poziomf
.Każde nowe wywołanie
fib2
wydaje 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ścin
(dzięki Vitusowi i Tichonowi za zwrócenie na to uwagi). Z pierwszą definicją nien
można polegać, az trzecią jest zależność, ale każde oddzielne wywołaniefib3
wywołań, dof
których należy uważać, aby wywołać definicje tylko z zakresu tego samego poziomu, wewnętrznego dla tego konkretnego wywołaniafib3
, więc to samoxs
dostaje się ponownie wykorzystane (tj. udostępnione) dla tego wywołaniafib3
.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
n
powią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 polimorficznegofib3
wykazuje udostępnianie lokalne ifib2
brak 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. :)
źródło
fib'
jest przedefiniowana dla każdego,n
a zatemfib'
wfib 1
≠fib'
infib 2
, co również oznacza, że listy są różne. Nawet jeśli naprawisz typ jako monomorficzny, nadal będzie wykazywał takie zachowanie.where
klauzule wprowadzają udostępnianie podobnie jaklet
wyrażenia, ale mają tendencję do ukrywania problemów, takich jak ten. Przepisując to nieco dokładniej, otrzymujesz to: hpaste.org/71406Int -> Integer
), Tofib2
działa w czasie wykładniczymfib1
ifib3
oba działają w czasie liniowym, alefib1
są również zapamiętywane - ponownie, ponieważ dlafib3
lokalnych definicji są przedefiniowane dla każdegon
.pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]
chcemy,pwr xs
aby były obliczane niezależnie, dwukrotnie, aby można było zbierać śmieci w locie, gdy są produkowane i konsumowane.Nie jestem do końca pewien, ale oto zgadywanie:
Kompilator zakłada, że
fib n
może to być inne na innymn
i dlatego za każdym razem musiałby ponownie obliczyć listę. W końcu bity wwhere
instrukcji 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ścin
przekazanej 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ż
fib
wersja 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) .
źródło
fib' n
może być inny na innymn
”?fib
, w tymfib'
, może być różne na każdym innymn
. Myślę, że oryginalny przykład jest trochę zagmatwany, ponieważfib'
zależy również od własnego,n
który rzuca cień na drugin
.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
i takie ograniczenie zostaje ustawione domyślnie (w przypadku braku domyślnej deklaracji mówiącej inaczej) na
Integer
, ustalając typ jakoZatem 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).
źródło
fib 1000000
wiele 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.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:
zipWith to funkcja ze standardowego Prelude:
Test:
Wynik:
Upłynął czas: 0,00018s
źródło