Byłem trochę zdezorientowany dokumentacją fix
(chociaż myślę, że rozumiem teraz, co ma robić), więc spojrzałem na kod źródłowy. To mnie bardziej zdezorientowało:
fix :: (a -> a) -> a
fix f = let x = f x in x
Jak dokładnie zwraca to stały punkt?
Postanowiłem wypróbować to w linii poleceń:
Prelude Data.Function> fix id
...
I tam wisi. Aby być uczciwym, to jest na moim starym Macbooku, który jest trochę powolny. Jednak ta funkcja nie może być zbyt kosztowna obliczeniowo, ponieważ cokolwiek przekazane do id zwraca to samo (nie wspominając o tym, że nie pochłania czasu procesora). Co ja robię źle?
haskell
fixpoint-combinators
letrec
Jason Baker
źródło
źródło
fix error
ghci i poczuć się dobrze ze sobą”.fix
jakofix f = f (fix f)
. Krótki, prosty, działa i identyczny z definicją matematyczną.fix (1:) !! (10^8)
. Oryginał robi to w stałej pamięci, twoja zajmuje pamięć liniową (co też sprawia, że jest trochę wolniejszy). Oznacza to, że użycie let „wiąże mocniejszy węzeł” i pozwala na wygenerowanie okrągłej struktury danych, podczas gdy twoja nie.fix
też wymyślić na nowo ! pomogli mifix
dużo zrozumieć .Odpowiedzi:
Nie robisz nic złego.
fix id
jest nieskończoną pętlą.Kiedy mówimy, że
fix
zwraca najmniej ustalony punkt funkcji, mamy na myśli to w sensie teorii domeny . Więcfix (\x -> 2*x-1)
się nie wróci1
, bo chociaż1
jest stałym punktem tej funkcji, to nie jest przynajmniej jeden w zamawiania domeny.Nie mogę opisać kolejności domen w jednym lub dwóch akapitach, więc odsyłam do powyższego linku do teorii domen. Jest to doskonały samouczek, łatwy do odczytania i dość pouczający. Gorąco polecam.
W przypadku widoku z wysokości 10 000 stóp
fix
jest to funkcja wyższego rzędu, która koduje ideę rekursji . Jeśli masz wyrażenie:let x = 1:x in x
Co daje nieskończoną listę
[1,1..]
, możesz powiedzieć to samo, używającfix
:fix (\x -> 1:x)
(Lub po prostu
fix (1:)
), które mówi: znajdź mi stały punkt(1:)
funkcji, IOW wartośćx
taką, żex = 1:x
... tak jak zdefiniowaliśmy powyżej. Jak widać z definicji,fix
to nic innego jak ta idea - rekursja zamknięta w funkcji.Jest to również prawdziwie ogólna koncepcja rekurencji - w ten sposób można napisać dowolną funkcję rekurencyjną, w tym funkcje wykorzystujące rekursję polimorficzną . Na przykład typowa funkcja Fibonacciego:
fib n = if n < 2 then n else fib (n-1) + fib (n-2)
Można napisać w
fix
ten sposób:fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))
Ćwiczenie: rozwiń definicję,
fix
aby pokazać, że te dwie definicjefib
są równoważne.Ale dla pełnego zrozumienia przeczytaj o teorii domeny. To naprawdę fajne rzeczy.
źródło
fix id
:fix
przyjmuje funkcję typua -> a
i zwraca wartość typua
. Ponieważid
jest polimorficzny dla dowolnegoa
,fix id
będzie miał typa
, czyli dowolną możliwą wartość. W Haskell jedyną wartością, która może być dowolnego typu, jest bottom, ⊥, i jest ona nie do odróżnienia od obliczeń nie kończących. Więcfix id
produkuje dokładnie to, co powinno, dolną wartość. Niebezpieczeństwofix
polega na tym, że jeśli your jest stałym punktem twojej funkcji, to z definicji jest najmniej stałym punktem, dlategofix
nie zakończy się.undefined
jest również wartością dowolnego typu. Można zdefiniowaćfix
jako:fix f = foldr (\_ -> f) undefined (repeat undefined)
._Y f = f (_Y f)
.Nie twierdzę, że w ogóle to rozumiem, ale jeśli to komuś pomaga ...
Rozważ definicję
fix
.fix f = let x = f x in x
. Zadziwiająca częśćx
jest zdefiniowana jakof x
. Ale pomyśl o tym przez chwilę.x = f x
Ponieważ x = fx, możemy podstawić wartość
x
po prawej stronie tego, prawda? Więc dlatego...x = f . f $ x -- or x = f (f x) x = f . f . f $ x -- or x = f (f (f x)) x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.
Tak więc sztuczka polega na tym, że aby zakończyć,
f
trzeba wygenerować jakąś strukturę, tak aby późniejszyf
wzorzec mógł dopasować tę strukturę i zakończyć rekursję, bez faktycznego dbania o pełną "wartość" swojego parametru (?)Chyba że, oczywiście, chcesz zrobić coś takiego, jak stworzenie nieskończonej listy, jak zilustrowano luqui.
Silnia wyjaśnienia TomMD jest dobra. Podpis typu poprawki to
(a -> a) -> a
. Innymi słowy, typ podpisu dla(\recurse d -> if d > 0 then d * (recurse (d-1)) else 1)
to . Więc możemy tak powiedzieć . W ten sposób fix przyjmuje naszą funkcję, która jest lub naprawdę, i zwróci wynik typu , innymi słowy, inną funkcję!(b -> b) -> b -> b
(b -> b) -> (b -> b)
a = (b -> b)
a -> a
(b -> b) -> (b -> b)
a
b -> b
Czekaj, myślałem, że powinien zwrócić stały punkt ... a nie funkcję. Cóż, w pewnym sensie (ponieważ funkcje to dane). Możesz sobie wyobrazić, że dało nam to ostateczną funkcję znajdowania silni. Daliśmy mu funkcję, która nie wiedziała, jak się powtarzać (stąd jeden z jej parametrów jest funkcją używaną do rekurencji), i
fix
nauczyliśmy ją, jak się powtarzać.Pamiętasz, jak powiedziałem, że
f
musi wygenerować jakąś strukturę, aby późniejf
można było dopasować wzorzec i zakończyć? Cóż, to chyba nie do końca w porządku. TomMD zilustrował, jak możemy rozszerzyć,x
aby zastosować funkcję i przejść do przypadku podstawowego. Do swojej funkcji użył warunku if / then i to właśnie powoduje zakończenie. Po wielokrotnych zamianachin
część całej definicjifix
ostatecznie przestaje być definiowana w kategoriachx
i wtedy jest obliczalna i kompletna.źródło
Potrzebujesz sposobu na zakończenie działania punktu stałego. Rozszerzając swój przykład, oczywiste jest, że się nie skończy:
fix id --> let x = id x in x --> id x --> id (id x) --> id (id (id x)) --> ...
Oto prawdziwy przykład użycia poprawki (uwaga, nie używam poprawki często i prawdopodobnie byłem zmęczony / nie martwiłem się o czytelny kod, kiedy to pisałem):
(fix (\f h -> if (pred h) then f (mutate h) else h)) q
WTF, mówisz! Cóż, tak, ale jest tutaj kilka naprawdę przydatnych punktów. Po pierwsze, pierwszym
fix
argumentem powinna być zwykle funkcja, która jest przypadkiem „rekurencyjnym”, a drugim argumentem są dane, na których należy działać. Oto ten sam kod, co nazwana funkcja:getQ h | pred h = getQ (mutate h) | otherwise = h
Jeśli nadal jesteś zdezorientowany, być może silnia będzie łatwiejszym przykładem:
fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120
Zwróć uwagę na ocenę:
fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 --> let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 --> let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 --> let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3
Och, czy właśnie to widziałeś? Stało
x
się to funkcją w naszymthen
oddziale.let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) --> let x = ... in 3 * x 2 --> let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->
W powyższym trzeba pamiętać
x = f x
, stąd dwa argumentyx 2
na końcu zamiast po prostu2
.let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->
I tu się zatrzymam!
źródło
fix
dla mnie sensowna. Moja odpowiedź w dużej mierze zależy od tego, co już powiedziałeś.id x
po prostu zmniejsza się dox
(co następnie zmniejsza się z powrotem doid x
). - Następnie w drugiej próbce (fact
), kiedyx
thunk jest najpierw wymuszony, wynikowa wartość jest zapamiętywana i ponownie używana. Ponowne obliczenie(\recurse ...) x
nastąpiłoby z definicją nieudostępnianiay g = g (y g)
, a nie z definicją udostępnianiafix
. - Wprowadziłem tutaj wersję próbną - możesz jej użyć, albo mogę wprowadzić zmianę, jeśli się zgodzisz.fix id
jest zmniejszona,let x = id x in x
wymusza również wartość aplikacjiid x
wewnątrzlet
ramki (thunk), więc zmniejsza się dolet x = x in x
i ta pętla. Wygląda jak to.fix
a Y jest bardzo wyraźne i ważne w Haskell. Nie widzę, czemu służy pokazanie niewłaściwej kolejności redukcji, podczas gdy poprawna jest jeszcze krótsza, dużo jaśniejsza i łatwiejsza do zrozumienia, i dobrze odzwierciedla to, co się właściwie dzieje.Jak rozumiem, znajduje wartość dla funkcji, taką, że wyprowadza to samo, co mu podajesz. Haczyk polega na tym, że zawsze wybierze undefined (lub nieskończoną pętlę, w haskell, undefined i infinite loop są takie same) lub cokolwiek, co ma najwięcej niezdefiniowanych w sobie. Na przykład z id,
λ <*Main Data.Function>: id undefined *** Exception: Prelude.undefined
Jak widać, undefined jest punktem stałym, więc
fix
wybierzemy to. Jeśli zamiast tego zrobisz (\ x-> 1: x).λ <*Main Data.Function>: undefined *** Exception: Prelude.undefined λ <*Main Data.Function>: (\x->1:x) undefined [1*** Exception: Prelude.undefined
Więc
fix
nie można wybrać niezdefiniowanego. Aby był nieco bardziej połączony z nieskończonymi pętlami.λ <*Main Data.Function>: let y=y in y ^CInterrupted. λ <*Main Data.Function>: (\x->1:x) (let y=y in y) [1^CInterrupted.
Znowu niewielka różnica. Więc jaki jest punkt stały? Spróbujmy
repeat 1
.λ <*Main Data.Function>: repeat 1 [1,1,1,1,1,1, and so on λ <*Main Data.Function>: (\x->1:x) $ repeat 1 [1,1,1,1,1,1, and so on
To jest to samo! Ponieważ jest to jedyny stały punkt,
fix
należy się na nim ustalić. Przepraszamyfix
, nie ma dla ciebie nieskończonych pętli lub niezdefiniowanych.źródło