webentwicklung-frage-antwort-db.com.de

Was sind freie Monaden?

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

351
David

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

Freie Monaden sind nur ein allgemeiner Weg, Funktoren in Monaden zu verwandeln. Das heißt, gegeben jeder Funktor fFree f ist eine Monade. Dies wäre nicht sehr nützlich, es sei denn, Sie erhalten ein Paar von 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 "einsteigen" und mit der zweiten können Sie "aussteigen".

Im Allgemeinen ist ein "freies X" ein Weg, um von einem Y zu einem X zu gelangen, ohne etwas mehr zu gewinnen, wenn X ein Y mit etwas zusätzlichem Zeug P ist.

Beispiele: Ein Monoid (X) ist eine Menge (Y) mit einer zusätzlichen Struktur (P), die im Grunde genommen besagt, dass es eine Operation (man kann sich 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 t wissen wir, dass [t] ist ein Monoid

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

und so sind Listen die "freien Monoiden" über Mengen (oder in Haskell-Typen).

Okay, freie Monaden sind die gleiche Idee. Wir nehmen einen Functor 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 Instanz Monad hat eine Ähnlichkeit mit der Instanz Monoid 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)
276
Philip JF

Hier ist eine noch einfachere Antwort: Eine Monade ist etwas, das "berechnet" wird, wenn der monadische Kontext durch join :: m (m a) -> m a reduziert wird (unter Hinweis darauf, dass >>= Als x >>= y = join (fmap y x) definiert werden kann). So führen Monaden den Kontext durch eine sequentielle Kette von Berechnungen: An jedem Punkt in der Reihe wird der Kontext aus dem vorherigen Aufruf mit dem nächsten reduziert.

A freie Monade erfüllt alle Monadengesetze, führt jedoch keine Kollapsbildung durch (d. H. Berechnung). Es baut einfach 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 erst danach aufgeschoben werden kann Der monadische Wert wurde erstellt.

392
John Wiegley

Ein freies Foo ist 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 nächsten wechselt.

Bei gegebenen Funktoren F : D -> C und G : C -> D sagen wir F -| G, F wird links an G angehängt, oder G wird rechts an F angehängt, wann immer a, b : F a -> b ist isomorph zu a -> G b, wobei die Pfeile aus den entsprechenden Kategorien stammen.

Formal wird ein freier Funktor einem vergesslichen Funktor gegenübergestellt.

Das freie Monoid

Beginnen wir mit einem einfacheren Beispiel, dem freien Monoid.

Nehmen Sie ein Monoid, das durch eine Carrier-Menge T definiert ist, eine Binärfunktion, um ein Elementpaar f :: T → T → T und ein unit :: T zu mischen, so dass Sie ein assoziatives Gesetz und ein Identitätsgesetz haben: f(unit,x) = x = f(x,unit).

Sie können einen Funktor U aus der Kategorie der Monoide erstellen (wobei Pfeile monoide Homomorphismen sind, dh sicherstellen, dass sie unit auf unit auf dem anderen Monoid abbilden, und das auch Sie können vor oder nach der Zuordnung zu dem anderen Monoid (ohne die Bedeutung zu ändern) zu der Kategorie von Mengen (wobei Pfeile nur Funktionspfeile sind) komponieren, die die Operation und unit 'vergessen' und Ihnen nur die Trägersammlung geben .

Dann können Sie einen Funktor F aus der Kategorie der Mengen zurück zu der Kategorie der Monoide definieren, die an diesen Funktor angrenzt. Dieser Funktor ist der Funktor, der eine Menge a auf das Monoid [a], wobei unit = [] und mappend = (++) abbildet.

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],(++),[])

Um zu zeigen, dass F kostenlos ist, muss gezeigt werden, dass es an U, einen vergesslichen Funktor, gebunden ist. Das heißt, wie oben erwähnt, müssen wir dies zeigen

F a → b ist isomorph zu a → U b

denken Sie daran, dass das Ziel von F in der Kategorie Mon von Monoiden liegt, in der Pfeile monoide Homomorphismen sind. Wir müssen also zeigen, dass ein monoider Homomorphismus aus [a] → b durch eine Funktion genau beschrieben werden kann von a → b.

In Haskell nennen wir die Seite davon, die in Set (äh, Hask, die Kategorie von Haskell-Typen, die wir so tun, als sei sie gesetzt) ​​lebt, nur foldMap, was wann spezialisiert von Data.Foldable auf Listen hat den Typ Monoid m => (a → m) → [a] → m.

Es gibt Konsequenzen, die sich daraus ergeben, dass es sich um eine Ergänzung handelt. Vor allem, wenn Sie vergessen, dann bauen Sie mit free auf, dann vergessen Sie noch einmal, 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) ~ UF und wir den identitätsmonoiden Homomorphismus von [a] an [a] über den Isomorphismus übergeben können, der unsere Adjunktion definiert, erhalten wir von diesem einen Listenisomorphismus [a] → [a] ist eine Funktion vom Typ a -> [a] und wird nur für Listen zurückgegeben.

Sie können dies alles direkter zusammenstellen, indem Sie eine Liste in diesen Begriffen beschreiben mit:

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

Die freie Monade

Also, was ist eine freie Monade ?

Nun, wir machen dasselbe wie zuvor, wir beginnen mit einem vergesslichen Funktor U aus der Kategorie der Monaden, in der Pfeile Monadenhomomorphismen sind, zu einer Kategorie der Endofunktoren, in der die Pfeile natürliche Transformationen sind, und wir suchen nach einem Funktor, der daneben bleibt dazu.

Wie verhält es sich also mit dem Begriff der freien Monade, wie er normalerweise verwendet wird?

Zu wissen, dass etwas eine freie Monade ist, sagt Free f, dass das Geben eines Monadenhomomorphismus aus Free f -> m dasselbe ist (isomorph zu) wie das Geben einer natürlichen Transformation (eines Funktorhomomorphismus) aus f -> m. Denken Sie daran, dass F a -> b isomorph zu a -> U b sein muss, damit F neben U bleibt. U hier zugeordnete Monaden zu Funktoren.

F ist mindestens isomorph zu dem Typ Free, den ich in meinem Paket free für Hackage verwende.

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

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

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

Cofree Comonaden

Wir können etwas Ähnliches konstruieren, indem wir uns die rechte Seite eines vergesslichen Funktors ansehen, der annimmt, dass er existiert. Ein cofree-Funktor ist einfach/direkt neben/an einen vergesslichen Funktor gebunden, und symmetrisch ist das Wissen, dass etwas eine cofree-Komonade ist, dasselbe wie das Wissen, dass das Geben eines comonaden Homomorphismus aus w -> Cofree f das gleiche ist wie das Geben einer natürlichen Transformation aus w -> f.

135
Edward KMETT

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


Sie wissen wahrscheinlich, was eine Monade ist und dass jede Monade eine bestimmte (nach dem Monadengesetz gültige) Implementierung von entweder fmap + join + return oder bind benötigt. + return.

Nehmen wir an, Sie haben einen Functor (eine Implementierung von fmap), aber der Rest hängt von den Werten und Auswahlen ab, die zur Laufzeit getroffen wurden. Dies bedeutet, dass Sie die Monad-Eigenschaften verwenden, aber die auswählen möchten Monaden-Funktionen danach.

Dies kann mit der freien Monade (Datenstruktur) geschehen, die den Functor (Typ) so umschließt, dass der join eher eine Stapelung dieser Functors als eine Reduktion ist.

Die tatsächlichen return und join, die Sie verwenden möchten, können jetzt 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 Typen zu erklären, können wir Functor f mit Monad m und b mit (m a):

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

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))

Pure ist analog zu Nil und Free ist analog zu Cons. Eine freie Monade speichert eine Liste von Funktoren anstelle einer Liste von Werten. Technisch könnten Sie freie Monaden mit einem anderen Datentyp implementieren, aber jede Implementierung sollte isomorph zu der obigen sein.

Sie verwenden freie Monaden, wenn Sie einen abstrakten Syntaxbaum benötigen. Der Basis-Funktor der freien Monade ist die Form jedes Schritts des Syntaxbaums.

Mein Beitrag , den jemand bereits verlinkt hat, gibt einige Beispiele, wie man abstrakte Syntaxbäume mit freien Monaden erstellt

56

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 a ist der Baumtyp, dessen Blätter den Typ a haben und dessen Knoten mit One, Two, Two' und Three. One- Knoten haben ein Kind, Two- und Two'- Knoten haben zwei untergeordnete Knoten und Three- Knoten haben drei untergeordnete Knoten und sind außerdem mit einem Int gekennzeichnet.

Free F ist eine Monade. return ordnet x dem Baum zu, der nur ein Blatt mit dem Wert x ist. t >>= f schaut sich jedes der Blätter an und ersetzt sie durch Bäume. Wenn das Blatt den Wert y hat, ersetzt es dieses Blatt durch den Baum f y.

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

21
Tom Ellis