Różnica między wolnymi monadami a fixpointami funktorów?

Question

Czytałem http://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.html, gdzie abstrakcyjne drzewo składniowe jest wyprowadzane jako darmowa monada funktora reprezentującego zbiór instrukcji. Zauważyłem, że bezpłatna monada Free nie różni się zbytnio od operatora fixpoint na funktorach Fix.

W artykule użyto operacji na monadach i składni do do budowania tych AST (punktów stałych) w zwięzły sposób. Zastanawiam się, czy to jedyna korzyść z bezpłatnej instancji Monady? Czy są jakieś inne interesujące aplikacje, które to umożliwia?

Answer 1

(NB ten łączy w sobie trochę z obu kopalni i @ komentarze Gabriela powyżej).

Jest to możliwe dla każdego mieszkańca punktu Fix ed z Functor się być nieskończony, czyli let x = (Fix (Id x)) in x === (Fix (Id (Fix (Id ...)))) jest tylko mieszkaniec Fix Identity. Free różni się natychmiast od Fix tym, że zapewnia co najmniej jednego użytkownika skończonego mieszkańca Free f. W rzeczywistości, jeśli Fix f ma nieskończoną liczbę mieszkańców, to Free f ma nieskończenie wielu skończonych mieszkańców.

Kolejnym natychmiastowym efektem ubocznym tej nieograniczoności jest to, że Functor f => Fix f nie jest już Functor. Musimy wdrożyć fmap :: Functor f => (a -> b) -> (f a -> f b), ale Fix ma "wypełnione wszystkie otwory" w f a, które zawierały a, więc nie mamy już żadnych a s do zastosowania naszej funkcji d do fmap.

Jest to ważne dla tworzenia Monad dlatego, że chcielibyśmy, aby wdrożyć return :: a -> Free f a i mieć, powiedzmy, to prawo trzymać fmap f . return = return . f, ale to nie ma sensu w Functor f => Fix f.

W jaki sposób Free "naprawić" te słabe punkty ed Fix? "Rozszerza" nasz funktor bazowy o konstruktor Pure. Tak więc, dla wszystkich Functor f, Pure :: a -> Free f a. To jest nasz gwarantowany, skończony mieszkaniec tego typu. To również natychmiast daje nam dobrze zachowaną definicję return.

return = Pure 

Więc można by pomyśleć o tym, jak dodatkowo wyjmując potencjalnie nieskończoną „drzewo” zagnieżdżonych Functor s stworzonych przez Fix i mieszanie w pewnej liczbie „żywych” pąków, reprezentowanej przez Pure. Tworzymy nowe pąki przy użyciu return, które mogą być interpretowane jako obietnica, że ​​"powrócą" do tego pączka później i dodadzą więcej obliczeń. Dokładnie to robi flip (>>=) :: (a -> Free f b) -> (Free f a -> Free f b). Biorąc pod uwagę funkcję "kontynuacji" f :: a -> Free f b, która może być zastosowana do typów a, cofamy nasze drzewo, powracając do każdego Pure a i zastępując je kontynuacją obliczoną jako f a. To pozwala nam "wyhodować" nasze drzewo.

---

Teraz Free jest wyraźnie bardziej ogólne niż Fix. Do kierowania tym domem można zobaczyć dowolny typ Functor f => Fix f jako podtyp odpowiedniego Free f a! Po prostu wybierz a ~ Void, gdzie mamy data Void = Void Void (tj. Typ, który nie może być skonstruowany, jest pusty, nie ma instancji).

Żeby było jasne, możemy złamać nasze Fix „D Functor S z break :: Fix f -> Free f a a następnie spróbować odwrócić ją affix :: Free f Void -> Fix f.

break (Fix f) = Free (fmap break f) 
affix (Free f) = Fix (fmap affix f) 

Uwaga pierwszy affix nie trzeba obsłużyć sprawę Pure x ponieważ w tym przypadku x :: Void, a tym samym nie może naprawdę tam być, więc Pure x jest absurdem, a my po prostu zignorować.

Należy również pamiętać, że break „s typ zwracany jest mało subtelny, gdyż typ a pojawia się tylko w rodzaju powrotu, Free f a tak, że jest to całkowicie niedostępne dla każdego użytkownika break. "Całkowicie niedostępne" i "nie można utworzyć wystąpienia" dają nam pierwszą wskazówkę, że pomimo typów, affix i break są odwrócone, ale możemy to po prostu udowodnić.

(break . affix) (Free f) 
===          [definition of affix] 
break (Fix (fmap affix f)) 
===          [definition of break] 
Free (fmap break (fmap affix f)) 
===          [definition of (.)] 
Free ((fmap break . fmap affix) f) 
===          [functor coherence laws] 
Free (fmap (break . affix) f) 

który powinien pokazać (ko-indukcyjnie, albo po prostu intuicyjnie, być może), że (break . affix) jest tożsamość. Drugi kierunek przebiega w całkowicie identyczny sposób.

Mam nadzieję, że to pokazuje, że Free f jest większa niż Fix f dla wszystkich Functor f.

---

Dlaczego więc warto korzystać z Fix? Cóż, czasami potrzebujesz tylko właściwości Free f Void z powodu jakiegoś efektu ubocznego nakładania warstw na warstwy f. W tym przypadku, wywołanie go pod numerem Fix f uściśla, że ​​nie powinniśmy starać się nad tym typem. Ponadto, ponieważ Fix jest po prostu newtype, kompilator może łatwiej kompilować warstwy Fix, ponieważ i tak odgrywa rolę semantyczną.

---

• Uwaga: możemy bardziej formalnie mówić o tym, jak Void i forall a. a są izomorficzne typy, aby zobaczyć więcej wyraźnie, jak rodzaje affix i break są harmonijne. Na przykład mamy absurd :: Void -> a jako absurd (Void v) = absurd v i unabsurd :: (forall a. a) -> Void jako unabsurd a = a. Ale te stają się trochę głupie.

Answer 2

Istnieje głębokie i "proste" połączenie.

Jest to konsekwencja adjoint functor theorem, lewe elementy pomocnicze zachowują początkowe obiekty: L 0 ≅ 0.

Kategorycznie, Free f jest funktorem z kategorii do jego algeb F (Free f jest lewostronny dla zapominalskiego funktora idącego w drugą stronę "rundy").Praca w HASK nasz początkowy algebra jest Void

Free f Void ≅ 0 

i początkowa algebra w kategorii F-algebr jest Fix f: Free f Void ≅ Fix f

import Data.Void 
import Control.Monad.Free 

free2fix :: Functor f => Free f Void -> Fix f 
free2fix (Pure void) = absurd void 
free2fix (Free body) = Fix (free2fix <$> body) 

fixToFree :: Functor f => Fix f -> Free f Void 
fixToFree (Fix body) = Free (fixToFree <$> body) 

Podobnie prawy adjoints (Cofree f, funktorem z Hask do kategorii F-co algebras) zachowuje końcowe obiekty: R 1 ≅ 1.

W HASK to jednostka: () i ostateczny cel F- wspólnie algebry jest również Fix f (są zbieżne w Hask), więc mamy: Cofree f() ≅ Fix f

import Control.Comonad.Cofree 

cofree2fix :: Functor f => Cofree f() -> Fix f 
cofree2fix (() :< body) = Fix (cofree2fix <$> body) 

fixToCofree :: Functor f => Fix f -> Cofree f() 
fixToCofree (Fix body) =() :< (fixToCofree <$> body) 

---

Zobacz jak podobne są definicje!

newtype Fix f 
    = Fix (f (Fix f)) 

Fix f jest Free f bez zmiennych.

data Free f a 
    = Pure a 
    | Free (f (Free f a)) 

Fix f jest Cofree f z wartościami manekina.

data Cofree f a 
    = a <: f (Cofree f a)