Die freie Struktur -Seite im Haskell-Wiki definiert eine Funktion zum Konvertieren einer Funktorinstanz in eine freie Monade:
%Vor% Dann sagen Sie inj [1,2,3] , hat (Num t) => Free [] t . Wie definiere ich eine Funktion, um etwas wie inj [1,2,3] zurück zu [1,2,3] zu bringen?
Wie @sclv sagt, gibt es im allgemeinen Fall keine Möglichkeit, direkt von der freien Monade eines Funktors zurück in den Funktor zu konvertieren. Warum nicht?
Wenn Sie sich an die Seite "free structures" erinnern, die Sie verlinkt haben, spricht sie zuerst von freien monoids , bevor Sie dasselbe Konzept auf Monaden ausdehnen. Das freie Monoid für einen Typ ist eine Liste; eine äquivalente Funktion "zurückkonvertieren" würde in diesem Fall ein freies Monoid mit dem Typ [a] zu einem einzelnen Element mit dem Typ a machen. Dies ist offensichtlich auf zwei verschiedene Arten nicht durchführbar: Wenn die Liste leer ist, kann sie nichts zurückgeben; und wenn die Liste mehrere Elemente hat, muss sie alle bis auf eins verwerfen.
Die Konstruktion einer freien Monade ist ähnlich und weist ein ähnliches Problem auf. Eine freie Monade wird durch Funktorkomposition definiert, die genau wie die normale Funktionszusammensetzung außer dem -Typkonstruktor ist. Wir können Funktorzusammensetzung nicht direkt in Haskell schreiben, aber genau wie f . g bedeutet \x -> f (g x) , können wir die Anwendung des Typkonstruktors verschachteln. Wenn Sie beispielsweise Maybe mit sich selbst zusammenstellen, erhalten Sie einen Typ wie Maybe (Maybe a) .
Mit anderen Worten, wo ein einfacher Funktor eine parametrisierte Struktur irgendeiner Art beschreibt, beschreibt die freie Monade dieses Funktors diese Struktur, die in sich selbst in beliebiger Tiefe verschachtelt ist.
Wenn wir also Free [] Int betrachten, könnte es ein einzelnes Int , eine Liste von Int s, eine Liste von Listen von Ints usw. sein.
So wie wir können nur ein freies Monoid (Liste) direkt in ein einzelnes Element umwandeln, wenn die Liste genau ein Element lang ist , können wir nur eine freie Monade direkt in den darunterliegenden Funktor konvertieren Wenn die Verschachtelung genau eine Ebene tief ist .
Wenn Sie an allgemeinen Wegen interessiert sind, Dinge aus einer freien Monade herauszuholen, müssen Sie etwas weiter gehen - eine Art rekursive faltenartige Operation, um die Struktur zu reduzieren.
Im speziellen Fall der freien Monade für Listen gibt es einen offensichtlichen Ansatz - rekursiv die Struktur abflachen, indem Sie die Konstruktoren Roll und Return entfernen und die Listen fortfahren, während Sie fortfahren. Es kann auch aufschlussreich sein, darüber nachzudenken, warum dieser Ansatz in diesem Fall funktioniert und wie er sich auf die Struktur von Listen bezieht.
Das erste, was zu beobachten ist, ist, dass eine Variation von inj Free zu etwas macht, das fast ein Monad Transformer ist.
Ich verwende Control.Monad.Free , von meinem kostenlosen Paket auf Hacker, um alles hier nicht zu wiederholen. Dies bedeutet, dass Roll wird Free und Return stattdessen im folgenden Code Pure relativ zur Version im Wiki genannt wird.
Sie können jedoch nicht in die andere Richtung für eine beliebige Functor gehen. Wenn Sie jedoch eine Instanz von Monad auf m haben, können Sie die Aufhebung rückgängig machen, indem Sie Free m auf eine einzelne Ebene der zugrunde liegenden Monade m ! Reduzieren.
Der Name wurde gewählt, weil dies eine Zurückziehung von lift ist. So genannt, weil
gilt wie in
gezeigt %Vor%, damit die Funktion retract die Arbeit von lift rückgängig macht.
Seit fmap = liftM gilt dies auch für inj .
Beachten Sie, dass lift . retract nicht id ist. Es gibt einfach nicht genug Platz, um alles in den dazwischenliegenden Typ zu setzen - die Verwendung der Monade zerschlägt alles flach - aber lift . retract . lift . retract = lift . retract enthält, weil lift . retract . lift . retract = lift . id . retract = lift . retract , also lift . retract ist idempotent.
Ich werde jetzt tatsächlich retract zum kostenlosen Paket hinzufügen. Ich brauchte es kürzlich für einen Artikel, den ich sowieso schreibe.
Ich verstehe nicht, warum Sie nach dieser Funktion fragen, und es gibt im Allgemeinen keine einzige Funktion vom Typ Free f a -> f a . Allerdings ist eine Umkehrung zu inj - was bedeutet, dass es eine Funktion dieses Typs gibt wenn Sie wissen, dass die Struktur eine äußere Rolle mit einer ist Schicht der Rückkehr. Wenn es tiefere Roll s gibt, dann wird dies mit Musterübereinstimmungsfehlern fehlschlagen, also ist es eine Art dummer Sache, mit der man anfangen soll. Aber hier gehts: