Was sind freie Monaden?

Ich habe den Begriff gesehen Freie Monad Pop - up jeden jetzt und dann für einige Zeit, aber jeder scheint nur zu benutzen / diskutieren sie , ohne eine Erklärung zu geben , was sie sind. Also: Was sind freie Monaden? (Ich würde sagen, ich bin mit Monaden und den Grundlagen von Haskell vertraut, habe aber nur sehr grobe Kenntnisse der Kategorietheorie.)

Die Antwort von Edward Kmett ist offensichtlich großartig. Aber es ist ein bisschen technisch. Hier ist eine vielleicht zugänglichere Erklärung.

Kostenlose Monaden sind nur eine allgemeine Methode, um Funktoren in Monaden zu verwandeln. Das heißt, vorausgesetzt, jeder Funktor f Free fist eine Monade. Dies wäre nicht sehr nützlich, es sei denn, Sie erhalten zwei Funktionen

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

Mit der ersten können Sie in Ihre Monade "hineinkommen", und mit der zweiten können Sie "herauskommen".

Im Allgemeinen ist ein "freies X" eine Möglichkeit, von einem Y zu einem X zu gelangen, ohne etwas zu gewinnen, wenn X ein Y mit einigen zusätzlichen Dingen P ist.

Beispiele: Ein Monoid (X) ist eine Menge (Y) mit einer zusätzlichen Struktur (P), die im Grunde sagt, dass es eine Operation (Sie können sich eine Addition vorstellen) und eine Identität (wie Null) hat.

Damit

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

Jetzt kennen wir alle Listen

data [a] = [] | a : [a]

Nun, bei jedem Typ, den twir kennen, [t]ist das ein Monoid

instance Monoid [t] where
  mempty   = []
  mappend = (++)

und so sind Listen das "freie Monoid" über Mengen (oder in Haskell-Typen).

Okay, freie Monaden sind die gleiche Idee. Wir nehmen einen Funktor und geben eine Monade zurück. In der Tat, da Monaden als Monoide in der Kategorie der Endofunktoren angesehen werden können, die Definition einer Liste

data [a] = [] | a : [a]

sieht der Definition von freien Monaden sehr ähnlich

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

und die MonadInstanz hat eine Ähnlichkeit mit der MonoidInstanz für Listen

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

Jetzt bekommen wir unsere beiden Operationen

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)

Hier ist eine noch einfachere Antwort: Eine Monade ist etwas, das "berechnet" wird, wenn der monadische Kontext durch reduziert wird join :: m (m a) -> m a(wobei daran erinnert wird, dass >>=dies definiert werden kann alsx >>= y = join (fmap y x) ). So führen Monaden den Kontext durch eine sequentielle Kette von Berechnungen: Denn an jedem Punkt der Reihe wird der Kontext des vorherigen Aufrufs mit dem nächsten reduziert.

Eine freie Monade erfüllt alle Monadengesetze, kollabiert jedoch nicht (dh berechnet). Es baut nur eine verschachtelte Reihe von Kontexten auf. Der Benutzer, der einen solchen freien monadischen Wert erstellt, ist dafür verantwortlich, etwas mit diesen verschachtelten Kontexten zu tun, sodass die Bedeutung einer solchen Komposition bis zur Erstellung des monadischen Werts verschoben werden kann.

Ein freies Foo ist zufällig die einfachste Sache, die alle 'Foo'-Gesetze erfüllt. Das heißt, es erfüllt genau die Gesetze, die notwendig sind, um ein Foo zu sein, und nichts Besonderes.

Ein vergesslicher Funktor ist einer, der einen Teil der Struktur "vergisst", wenn er von einer Kategorie zur anderen wechselt.

Gegebene Funktoren F : D -> C, und G : C -> Dwir sagen F -| G, Fist links neben Goder Grechts neben, Fwann immer a, b: F a -> bisomorph ist a -> G b, wo die Pfeile aus den entsprechenden Kategorien stammen.

Formal bleibt ein freier Funktor neben einem vergesslichen Funktor.

Das freie Monoid

Beginnen wir mit einem einfacheren Beispiel, dem freien Monoid.

Nehmen Sie ein Monoid, das durch einen Trägersatz definiert ist T, eine binäre Funktion, um ein Elementpaar zusammenzufügen f :: T → T → T, und a unit :: T, so dass Sie ein assoziatives Gesetz und ein Identitätsgesetz haben : f(unit,x) = x = f(x,unit).

Sie können einen Funktor machen Uaus der Kategorie der Monoide (wo Pfeile Monoid Homomorphismen sind, das heißt, sie sicherstellen , dass sie Karte unitzu unitauf der anderen Monoid, und dass Sie vor oder nach der Abbildung auf die andere Monoid ohne Änderung Bedeutung komponieren kann) in die Kategorie von Sätzen (wobei Pfeile nur Funktionspfeile sind), die die Operation "vergessen" unitund Ihnen nur den Trägersatz geben.

Anschließend können Sie einen Funktor Faus der Kategorie der Sets zurück in die Kategorie der Monoide definieren, die neben diesem Funktor verbleibt. Dieser Funktor ist der Funktor, der eine Menge adem Monoid zuordnet [a], wo unit = []und mappend = (++).

Um unser bisheriges Beispiel in Pseudo-Haskell zu überprüfen:

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

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

Dann, um zu zeigen, Fist kostenlos, müssen wir zeigen, dass es neben Ueinem vergesslichen Funktor bleibt, das heißt, wie wir oben erwähnt haben, müssen wir das zeigen

F a → b ist isomorph zu a → U b

Denken Sie nun daran, dass das Ziel von Fin der Kategorie Monder Monoide liegt, in der Pfeile Monoidhomomorphismen sind. Wir müssen also zeigen, dass ein Monoidhomomorphismus von [a] → bdurch eine Funktion von genau beschrieben werden kann a → b.

In Haskell nennen wir die Seite davon, in der wir leben Set(ähm, Haskdie Kategorie der Haskell-Typen, die wir vorgeben, ist Set), nur foldMapdie, wenn sie von Data.Foldableauf Listen spezialisiert ist, Typ hat Monoid m => (a → m) → [a] → m.

Daraus ergeben sich Konsequenzen als Ergänzung. Insbesondere, wenn Sie vergessen, dann bauen Sie mit kostenlos auf, dann vergessen Sie wieder, es ist genau so, wie Sie es einmal vergessen haben, und wir können dies verwenden, um den monadischen Join aufzubauen. da UFUF~ U(FUF)~ UFund wir den identitätsmonoiden Homomorphismus von [a]bis [a]durch den Isomorphismus übergeben können, der unsere Adjunktion definiert, erhalten Sie, dass ein Listenisomorphismus von [a] → [a]eine Funktion des Typs ista -> [a] , und dies ist nur eine Rückgabe für Listen.

Sie können dies alles direkter zusammenstellen, indem Sie eine Liste folgendermaßen beschreiben:

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

Die freie Monade

Was ist also eine freie Monade? ?

Nun, wir machen das Gleiche wie zuvor. Wir beginnen mit einem vergesslichen Funktor U von der Kategorie der Monaden, bei der Pfeile Monadenhomomorphismen sind, zu einer Kategorie von Endofunktoren, bei denen die Pfeile natürliche Transformationen sind, und suchen nach einem Funktor, der nebeneinander bleibt dazu.

Wie hängt das mit der Vorstellung einer freien Monade zusammen, wie sie normalerweise verwendet wird?

Zu wissen, dass etwas eine freie Monade ist Free f, sagt Ihnen, dass das Geben eines Monadenhomomorphismus von Free f -> mdasselbe ist (isomorph zu) wie das Geben einer natürlichen Transformation (eines Funktorhomomorphismus) von f -> m. Denken Sie daran, F a -> bdass es isomorph zu sein muss, a -> U bdamit F neben U bleibt. Hier werden Monaden auf Funktoren abgebildet.

F ist mindestens isomorph zu dem FreeTyp, den ich in meinem freePaket für Hackage verwende.

Wir könnten es auch in engerer Analogie zum obigen Code für die freie Liste konstruieren, indem wir es definieren

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

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

Kaffeefreie Comonaden

Wir können etwas Ähnliches konstruieren, indem wir den richtigen Zusatz zu einem vergesslichen Funktor betrachten, vorausgesetzt, er existiert. Ein Cofree-Funktor ist einfach / richtig neben einem vergesslichen Funktor, und aus Symmetriegründen ist das Wissen, dass etwas eine Cofree-Comonade ist, dasselbe wie das Wissen, dass das Geben eines Comonad-Homomorphismus aus w -> Cofree fdasselbe ist wie das Geben einer natürlichen Transformation von w -> f.

Die freie Monade (Datenstruktur) ist für die Monade (Klasse) wie die Liste (Datenstruktur) für die Monoid (Klasse): Es ist die triviale Implementierung, bei der Sie anschließend entscheiden können, wie der Inhalt kombiniert werden soll.

Sie wissen wahrscheinlich, was eine Monade ist und dass jede Monade eine spezifische (monadengesetzliche) Implementierung von beiden benötigt fmap + join+ returnoder bind+ benötigt return.

Nehmen wir an, Sie haben einen Functor (eine Implementierung von fmap), aber der Rest hängt von den zur Laufzeit getroffenen Werten und Auswahlmöglichkeiten ab. Dies bedeutet, dass Sie die Monad-Eigenschaften verwenden möchten, aber anschließend die Monad-Funktionen auswählen möchten.

Dies kann mit der Free Monad (Datenstruktur) erfolgen, die den Functor (Typ) so umschließt, dass joines sich eher um eine Stapelung dieser Funktoren als um eine Reduzierung handelt.

Das Real returnund das, was joinSie verwenden möchten, können nun als Parameter für die Reduktionsfunktion angegeben werden foldFree:

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

Um die Art zu erklären, können wir ersetzen Functor fmit Monad mund bmit (m a):

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

Eine Haskell-freie Monade ist eine Liste von Funktoren. Vergleichen Sie:

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

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

Pureist analog zu Nilund Freeist analog zu Cons. Eine kostenlose Monade speichert eine Liste von Funktoren anstelle einer Liste von Werten. Technisch gesehen könnten Sie freie Monaden mit einem anderen Datentyp implementieren, aber jede Implementierung sollte isomorph zu der obigen sein.

Sie verwenden kostenlose Monaden, wenn Sie einen abstrakten Syntaxbaum benötigen. Der Basisfunktor der freien Monade ist die Form jedes Schritts des Syntaxbaums.

Mein Beitrag , den bereits jemand verlinkt hat, enthält einige Beispiele für das Erstellen abstrakter Syntaxbäume mit freien Monaden

Ich denke, ein einfaches konkretes Beispiel wird helfen. Angenommen, wir haben einen Funktor

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

mit dem Offensichtlichen fmap. Dann Free F aist die Art der Bäume , deren Blätter haben Art aund deren Knoten sind verschlagwortet mit One, Two, Two'und Three. One-Knoten haben ein Kind, Two- und Two'-Knoten haben zwei Kinder und Three-Knoten haben drei und sind auch mit einem gekennzeichnet Int.

Free Fist eine Monade. returnwird xdem Baum zugeordnet, der nur ein Blatt mit Wert ist x. t >>= fschaut auf jedes der Blätter und ersetzt sie durch Bäume. Wenn das Blatt einen Wert yhat, ersetzt es dieses Blatt durch den Baum f y.

Ein Diagramm macht dies klarer, aber ich habe nicht die Möglichkeit, einfach eines zu zeichnen!