Czym są darmowe monady?

Oto jeszcze prostsza odpowiedź: Monada jest czymś, co "oblicza", gdy kontekst monadyczny jest zwinięty przez join :: m (m a) -> m a (przypominając, że >>= można zdefiniować jako (join .) . flip fmap). W ten sposób monady przenoszą kontekst poprzez sekwencyjny łańcuch obliczeń: ponieważ w każdym punkcie serii kontekst z poprzedniego wywołania jest zwijany z następnym.

A wolna monada spełnia wszystkie prawa monady, ale nie wykonuje żadnych upadków (tj. obliczeń). Po prostu buduje zagnieżdżoną serię konteksty. Użytkownik, który tworzy taką wolną wartość monadyczną, jest odpowiedzialny za zrobienie czegoś z tymi zagnieżdżonymi kontekstami, dzięki czemu znaczenie takiej kompozycji może zostać odroczone do momentu utworzenia wartości monadycznej.

Wolna foo jest najprostszą rzeczą, która spełnia wszystkie prawa "foo". Oznacza to, że spełnia dokładnie prawa niezbędne do bycia foo i nic dodatkowego.

Funkcja zapominająca to taka, która "zapomina" część struktury, przechodząc z jednej kategorii do drugiej.

Biorąc pod uwagę funktory F : D -> C i G : C -> D, mówimy F -| G, F G, lub G jest tuż przy F gdy forall a, b: {[10] } jest izomorficzny do a -> G b, gdzie strzałki z odpowiednich kategorii.

Formalnie funktor wolny pozostawia się przy funktorze zapominalskim.

Wolny Monoid

Zacznijmy od prostszego przykładu, wolnego monoidu.

Weźmy monoid, który jest zdefiniowany przez pewien zbiór nośników T, funkcję binarną, która masuje parę elementów razem f :: T → T → T i unit :: T, tak że mamy prawo asocjacyjne i prawo tożsamości: f(unit,x) = x = f(x,unit).

Możesz zrobić funktor U z Kategoria monoidów (gdzie strzałki są homomorfizmami monoidów, to znaczy zapewniają, że odwzorowują unit do unit na drugiej monoidzie, i że można komponować przed lub po mapowaniu do drugiej monoidy bez zmiany znaczenia) do kategorii zbiorów (gdzie strzałki są po prostu strzałkami funkcyjnymi), która "zapomina" o operacji i unit, i po prostu daje zbiór nośnika.

Następnie można zdefiniować funktor F z kategorii zbiorów z powrotem do kategorii monoidów, które pozostają / align = "left" / Funkcja ta jest funkcją odwzorowującą zbiór a na monoid [a], gdzie unit = [] i mappend = (++).

Aby przejrzeć nasz przykład do tej pory, w pseudo-Haskell:

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

Następnie, aby pokazać {[6] } jest wolny, musimy wykazać, że jest on pozostawiony przy U, zapominalskim funktorem, to znaczy, jak wspomnieliśmy powyżej, musimy pokazać, że

F a → b jest izomorficzna do a → U b

Pamiętaj, że cel F jest w kategorii Mon monoidów, gdzie strzałki są homomorfizmami monoidalnymi, więc musimy pokazać, że homomorfizm monoidalny z [a] → b może być dokładnie opisany przez funkcję z a → b.

W Haskell nazywamy stronę tego, która mieszka w Set (er, Hask, Kategoria typów Haskell, którą udajemy, że jest ustawiona), po prostu foldMap, która gdy jest wyspecjalizowana z Data.Foldable Do List, ma typ Monoid m => (a → m) → [a] → m.

Są konsekwencje, które wynikają z tego, że jest to adjunkcja. Zwłaszcza, że jeśli zapomnisz, to zbuduj za darmo, potem zapomnij ponownie, to tak, jak zapomniałeś raz, i możemy użyć tego do zbudowania monadycznego połączenia. od UFUF ~ U(FUF) ~ UF, i możemy przejść w identyczności homomorfizm monoidalny z [a] do {[22] } poprzez izomorfizm definiujący nasze przyporządkowanie, otrzymamy, że izomorfizm listy z [a] → [a] jest funkcją typu a -> [a], a to jest tylko zwrot dla list.

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

Na Free Monad

Więc czym jest wolna Monada ?

Cóż, robimy to samo, co robiliśmy wcześniej, zaczynamy od zapomnienia funktora U z kategorii monad, gdzie strzałki są homomorfizmami monad, do kategorii endofunktorów, gdzie strzałki są naturalnymi transformacjami, i szukamy funktora, który jest do tego powiązany.

Więc, jak to się ma do pojęcia wolnej monady, jak to jest zwykle używane?

Wiedząc, że coś jest wolnym monada, Free f, mówi, że dając homomorfizm monady z Free f -> m, jest tym samym (izomorficznym do), co dając przekształcenie naturalne (homomorfizm funktora) z f -> m. Pamiętaj, że F a -> b musi być izomorficzna do a -> U b, aby F pozostało przy U. U. tutaj odwzorowane monady na funktory.

F jest co najmniej izomorficzny do Free typu, którego używam w moim free pakiecie na hackage.

Moglibyśmy również skonstruować go w ściślejszej analogii do powyższego kodu dla wolnej listy, przez definiowanie

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Kofree Comonads

Możemy skonstruować coś podobnego, patrząc na odpowiedni dodatek do zapominającego funktora zakładając, że istnieje. Funktor kofree jest po prostu /prawym dopełnieniem / do zapominającego funktora, a przez symetrię, wiedząc, że coś jest kofree comonad jest tym samym, co wiedząc, że dając homomorfizm comonada z w -> Cofree f jest tym samym, co dając naturalną transformację z w -> f.

Wolna Monada (struktura danych) jest do monady (Klasa) jak lista (struktura danych) do Monoidy (klasa): jest to trywialna implementacja, w której możesz później zdecydować, w jaki sposób zawartość będzie łączona.

Prawdopodobnie wiesz, co to jest Monada i że każda Monada potrzebuje określonej (monad-law abiding) implementacji albo fmap + join + return lub bind + return.

Załóżmy, że masz funktor (implementację fmap), ale reszta zależy od wartości i wybory dokonane w czasie wykonywania, co oznacza, że chcesz móc korzystać z właściwości Monad, ale chcesz wybrać funkcje Monad później.

Można to zrobić za pomocą wolnej monady (struktury danych), która otacza funktor (typ) w taki sposób, że join jest raczej stosem tych funktorów niż redukcją.

Prawdziwe return i join, których chcesz użyć, mogą być teraz podane jako parametry funkcji redukcji foldFree:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

To wyjaśnij typy, możemy zastąpić Functor f Monad m i b (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

Haskell free monad jest listą funktorów. Porównaj:

data List a   = Nil    | Cons  a (List a  )

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

Pure jest analogiczne do Nil i {[3] } jest analogiczne do Cons. Darmowa monada przechowuje listę funktorów zamiast listy wartości. Technicznie można zaimplementować darmowe monady używając innego typu danych, jednak każda implementacja powinna być izomorficzna z powyższą.

Używasz darmowych monad, gdy potrzebujesz abstrakcyjnego drzewa składni. Podstawowym funktorem wolnej monady jest kształt każdego kroku składni drzewo.

Mój post , który ktoś już linkował, podaje kilka przykładów jak budować abstrakcyjne drzewa składniowe za pomocą darmowych monad

Myślę, że prosty konkretny przykład pomoże. Załóżmy, że mamy funktor

data F a = One a | Two a a | Two' a a | Three Int a a a

Z oczywistym fmap. Następnie Free F a jest typem drzew, których liście mają typ a i których węzły są oznaczone One, Two, Two' i Three. One - węzły mają jedno dziecko, Two - i Two' - węzły mają dwoje dzieci i Three - węzły mają trzy i są również oznaczone Int.

Free F to monada. return mapuje x do drzewa, które jest tylko liściem o wartości x. t >>= f wygląda na każdym z liści i zastępuje je drzewami. Gdy liść ma wartość y zastępuje ten liść drzewem f y.

Schemat sprawia, że jest to jaśniejsze, ale nie mam możliwości, aby łatwo go narysować!