Wizualizacja wolnej monady

Question

Myślę, że mam zgrubne wyobrażenie o tym, czym jest darmowa monada, ale chciałbym mieć lepszy sposób na jej wizualizację.

Ma sens, że wolne magmy są po prostu binarnymi drzewami, ponieważ jest to "ogólne", jak można bez utraty informacji.

Podobnie ma sens, że darmowe monoidy to tylko listy, ponieważ kolejność operacji nie ma znaczenia. Istnieje teraz redundancja w "drzewie binarnym", więc można ją po prostu spłaszczyć, jeśli ma to sens.

To ma sens, że wolne grupy niby wyglądać fraktale, z podobnego powodu: https://upload.wikimedia.org/wikipedia/en/e/e8/F2_Cayley_Graph.png i dostać się do innych grup, po prostu identyfikacji poszczególnych elementów grupy jako „ten sam” i mamy inne grupy.

Jak mam wizualizować darmową monadę? W tej chwili uważam to za najbardziej ogólne abstrakcyjne drzewo składniowe, które można sobie wyobrazić. Czy to w istocie jest? Czy mogę to uprościć?

Co więcej, co tracimy, przechodząc od bezpłatnej monady do listy lub innych monad? Co identyfikujemy, by być "tym samym"?

Doceniam wszystkie komentarze, które rzucają światło na to. Dzięki!

Answer 1

W tej chwili po prostu myślę o [darmowej monadzie] jako o najbardziej ogólnym abstrakcyjnym drzewie składni, które można sobie wyobrazić. Czy to w istocie jest? Czy mogę to uprościć?

Ty upraszczając go:

1. „Free monady” jest skrótem od „wolnej monady nad konkretnym funktora” lub typu Free f a danych, która w rzeczywistości jest inny wolny monada dla każdego wyboru f.
2. Nie ma jednej ogólnej struktury, którą mają wszystkie wolne monady. Ich struktura rozpada się na:
   • Co jest wkładem Free samego
   • Co jest wniesionego przez różnych wyborów dla f

Ale rzućmy innego podejścia. Nauczyłem się darmowych monad przez najpierw studiowanie blisko spokrewnionego operational monad, który ma bardziej jednolitą, łatwiejszą do wizualizacji strukturę. Gorąco polecam zapoznanie się z tym z samego linku.

Najprostszym sposobem definiowania monady operacyjnego jest tak:

{-# LANGUAGE GADTs #-} 

data Program instr a where 
    Return :: a -> Program instr a 
    Bind :: instr x     -- an "instruction" with result type `x` 
     -> (x -> Program instr a) -- function that computes rest of program 
     -> Program instr a   -- a program with result type `a` 

... gdzie parametr instr typ reprezentuje „instrukcja” typ monady, zazwyczaj GADT.Na przykład (zaczerpnięte z link):

data StackInstruction a where 
    Pop :: StackInstruction Int 
    Push :: Int -> StackInstruction() 

więc Program w monady operacyjnego, nieformalnie, będę wizualizować go jako „dynamiczny” listy instrukcji, gdzie wynik wyprodukowany przez wykonanie każdej instrukcji jest używane jako wejście do funkcji, która decyduje o "ogonie" "listy instrukcji". Konstruktor Bind paruje instrukcję z funkcją "wyboru ogona".

Wiele darmowych monad można również wizualizować w podobny sposób - można powiedzieć, że funktor wybrany dla danej bezpłatnej monady służy jako "zestaw instrukcji". Ale z darmowymi monadami "ogony" lub "dzieci" z "instrukcji" są zarządzane przez samą Functor. Tak prosty przykład (wzięty z Gabriel González's popular blog entry on the topic)

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

-- The `next` parameter represents the "tails" of the computation. 
data Toy b next = 
    Output b next 
    | Bell next 
    | Done 

instance Functor (Toy b) where 
    fmap f (Output b next) = Output b (f next) 
    fmap f (Bell next) = Bell (f next) 
    fmap _ Done = Done 

ile w monadzie operacyjny funkcja wykorzystywana do generowania „ogon” należy do Program typu (w konstruktora Bind) w postaci wolnej monadach ogony należą do typ "instrukcja"/Functor. To pozwala "instrukcjom" darmowej monady (analogia, która się teraz rozpada), aby mieć pojedynczy "ogon" (jak Output lub Bell), zero ogonków (jak Done) lub wiele ogonów, jeśli tak zdecydujesz. Lub w innym wspólnego wzorca, parametr next może być typem wynikiem funkcji wbudowanych:

data Terminal a next = 
    PutStrLn String next 
    | GetLine (String -> next) -- can't access the next "instruction" unless 
           -- you supply a `String`. 

instance Functor Terminal where 
    fmap f (PutStrLn str next) = PutStrLn str (f next) 
    fmap f (GetLine g) = GetLine (fmap f g) 

To, nawiasem mówiąc, jest zastrzeżenie mam od dawna do ludzi, którzy odnoszą się do zwolnienia lub monad operacyjnych " drzewa składniowe "- ich praktyczne użycie wymaga, aby" dzieci "węzła były niepoprawnie ukryte wewnątrz funkcji. Zazwyczaj nie można w pełni sprawdzić tego "drzewa"!

Tak naprawdę, kiedy do niego dojdziesz, wyobrażenie sobie darmową monadę sprowadza się całkowicie do struktury Functor, której używasz do parametryzowania. Niektóre wyglądają jak listy, niektóre wyglądają jak drzewa, a niektóre wyglądają jak "nieprzezroczyste drzewa" z funkcjami jak węzły. (Raz odpowiedział ktoś do mojego sprzeciwu nad linią jak „funkcja jest węzeł drzewa z tylu dzieci, ile jest możliwych argumentów.”)

Answer 2

może słyszeliście

Monada jest monoid w kategoria endofunctors

I wspomniano już, że monoids są tylko listy. Więc jesteś.

---

rozwinięcie tego kawałka:

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

nie jest normalną listę a, ale lista gdzie ogon jest zawinięty wewnątrz f.zobaczysz go, jeśli piszesz strukturę wartości wielu zagnieżdżonych wiąże:

pure x >>= f >>= g >>= h :: Free m a 

może doprowadzić do

Free $ m1 $ Free $ m2 $ Free $ m3 $ Pure x 
    where m1, m2, m3 :: a -> m a -- Some underlying functor "constructors" 

Jeśli m w przykładzie powyżej jest typ suma:

data Sum a = Inl a | Inr a 
    deriving Functor 

Wtedy lista jest właściwie drzewem, tak jak w każdym konstruktorze możemy rozgałęziać się w lewo lub w prawo.

---

Być może słyszeliście, że

aplikacyjnych jest monoid w kategorii endofunctors

... kategoria jest po prostu inna. Są ładne wizualizacje różnych darmowych kodowań aplikacyjnych w Roman Cheplyaka's blog post.

Tak bezpłatny Applicative to także lista. Sobie wyobrazić, że za pomocą heterogenicznej liście f a wartości, jednej funkcji:

x :: FreeA f a 
x = FreeA g [ s, t, u, v] 
    where g :: b -> c -> d -> e -> a 
      s :: f b 
      t :: f c 
      u :: f d 
      v :: f e 

W tym przypadku sama ogon nie jest zawinięty w f, ale każdy z elementów oddzielnie. To może lub nie pomoże zrozumieć różnicę między Applicative i Monad.

Uwaga, że ​​f nie musi być Functor, aby wykonać Applicative (FreeA f a), w przeciwieństwie do monady Free powyżej.

---

Istnieje również bezpłatny Functor

data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a 

co sprawia żadnych * -> * typ Functor. Porównaj to z bezpłatnym Applicative powyżej. W przypadku aplikacyjnym mieliśmy heterogeniczną listę długości n z f a wartości i funkcję n-ary łączącą je. Coyoneda jest 1-osobowym specjalnym opakowaniem z góry.

---

Możemy połączyć Coyoneda i Free aby Operational bezpłatny monady. I, jak mówi inna odpowiedź, ten jest trudny do wyobrażenia jako drzewo, ponieważ w grę wchodzą funkcje. OTOH możesz sobie wyobrazić te kontynuacje jako różne, magiczne strzały na twoim zdjęciu :)