Control.MonadPlus.Free ohne unnötige Verteilung

Question

Ich versuche, eine kostenlose Monade zu verwenden, um eine EDSL für den Aufbau UND/ODER Entscheidungsbäume wie Prolog, mit zugeordnet AND, und mplus auf OR zugeordnet. Ich möchte in der Lage sein, etwas wie A AND (B OR C) AND (D OR E) zu beschreiben, aber ich möchte nicht, dass die Verteilung dies in (A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E) umwandelt. Letztendlich möchte ich die AND/OR-Knoten in komprimierte Constraints in einem Constraint-Solver transformieren, ohne die kombinatorische Explosion in der Anzahl der Alternativen zu verursachen, mit denen der Solver umgehen soll.

In Control.MonadPlus.Free, Plus ms >>= f verursacht f an jede der Pure Blättern unter jedem monadisch in ms angewendet werden. Dies ist erforderlich, da f einen anderen Wert für jedes Pure Blatt ergeben kann, das ersetzt wird.

jedoch in Plus ms >> g, g kann nicht von einem der Blätter von ms beeinflusst werden, so dass es über die Plus Verteilung scheint überflüssig.

Durch Versuch und Irrtum, fand ich, dass ich die Control.MonadPlus.Free Monade mit einem neuen Then Konstruktor erweitern konnte:

data Free f a = Pure a 
       | Free (f (Free f a)) 
       | Then [Free f()] (Free f a) 
       | Plus [Free f a] 

Hier ist das neue Then Konstruktor hält eine Folge von Monaden, dessen Wert wir ignorieren, gefolgt von der letzte Monade, die den tatsächlichen Wert ergibt. Die neue Monad Instanz wie folgt aussieht:

instance Functor f => Monad (Free f) where 
    return = Pure 

    Pure a >>= f = f a 
    Free fa >>= f = Free $ fmap (>>= f) fa 
    Then ms m >>= f = Then ms $ m >>= f 
    Plus ms >>= f = Plus $ map (>>= f) ms 

    Pure a >> mb = mb 
    Then ms ma >> mb = Then (ms ++ [ma >>= (const $ return())]) mb 
    ma >> mb = Then [] ma >> mb 

Die >> Operator „Caps“ alle vorhandenen Blätter von Pure a mit Pure() ersetzt, die mit einer Kappe bedeckt Monade in die Liste anhängt, und ersetzt den Wert Monade mit dem neuen. Ich bin mir der Ineffizienz der Anhängen der neuen Monade mit ++ bewusst, aber ich denke, es ist so schlecht wie >>= seine neue Monade bis zum Ende der Kette mit fmap näht (und das Ganze kann mit Fortsetzungen neu geschrieben werden).

Scheint dies eine vernünftige Sache zu tun? Verstößt dies gegen die Monadengesetze (ist das wichtig?), Oder gibt es eine bessere Möglichkeit, das vorhandene Control.Monad.Free zu verwenden?

Answer 1

Sie möchten vielleicht einen Blick auf meine operational Paket, die eine andere Sicht auf freie Monaden ist.

Insbesondere sehen Sie sich das BreadthFirstParsing.hs Beispiel an. Es verfügt über einen mplus Betrieb, so dass >>=nicht automatisch darüber verteilen. Dies ermöglicht es Ihnen, Parser-Kombinatoren in einer Breite-zuerst-Weise zu implementieren.

übersetzt auf Control.Monad.Free, ist der Punkt, dass, wenn Sie den Funktors verwenden

data F b = MZero | MPlus b b 

dann Free F automatisch >>= über mplus verteilen wird. Sie haben die Funktors

data F b = MZero | forall a. MPlus (Free f a) (Free f a) (a -> b) 

stattdessen verwenden, wenn Sie eine Semantik für MPlus implementieren möchten, die nicht automatisch >>= verteilen.(Dies ist der Hauptgrund, warum ich meine funktionsfähige Bibliothek der freien Bibliothek vorziehe.)