Control.MonadPlus.Free bez niepotrzebnej dystrybucji

Question

Próbuję użyć darmowej monady do zbudowania EDSL do budowy drzewek decyzyjnych AND/OR takich jak Prolog, z >>= zamapowanych na ORAZ i mplus zamapowanych na OR. Chcę móc opisać coś w rodzaju A AND (B OR C) AND (D OR E), ale nie chcę, aby dystrybucja przekształciła to w (A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E). Ostatecznie chcę przekształcić węzły AND/OR w reifikowane wiązania w rozwiązaniu ograniczającym, bez powodowania kombinatorycznej eksplozji w liczbie alternatyw, którymi chcę się zająć przez solver.

W Control.MonadPlus.Free, Plus ms >>= f powoduje f być stosowane do każdego z Pure liści pod każdym monady w ms. Jest to konieczne, ponieważ f może przynieść inną wartość dla każdego liścia Pure, który zastępuje.

Jednak w Plus ms >> g, g nie mogą być dotknięte przez dowolny z liści ms, więc rozprowadzenie nad Plus wydaje się zbędne.

Metodą prób i błędów odkryłem, że mogę przedłużyć Control.MonadPlus.Free monady z nowym Then konstruktora:

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

Oto nowa Then konstruktor posiada sekwencję monad, których wartość możemy ignorować, a następnie przez ostatnia monada, która daje rzeczywistą wartość. Nowy Monad przykład wygląda następująco:

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 

The >> operator „czapki” istniejące listowie przez zastąpienie Pure a z Pure(), dołącza kaucyjna monady do listy, a zastępuje monady wartość z nową. Jestem świadomy nieskuteczności dołączania nowej monady z ++, ale myślę, że jest tak źle, jak >>= zszywanie nowej monady na końcu łańcucha z fmap (i całą rzecz można przepisać przy użyciu kontynuacji).

Czy wydaje się to rozsądną rzeczą do zrobienia? Czy to narusza prawa Monady (czy to ważne?), Czy istnieje lepszy sposób na wykorzystanie istniejącego Control.Monad.Free?

Answer 1

Możesz chcieć rzucić okiem na moją paczkę operational, która jest inną przygodą na darmowych monadach.

W szczególności spójrz na przykład BreadthFirstParsing.hs. Zawiera on operację mplus, dzięki czemu >>= nie jest automatycznie dystrybuowana. Pozwala to na implementowanie kombinatorów parsera w pierwszy sposób.

Przetłumaczony na Control.Monad.Free, chodzi o to, że jeśli używasz funktor

data F b = MZero | MPlus b b 

następnie Free F automatycznie dystrybuować >>= nad mplus. Musisz zamiast używać funktor

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

, jeśli chcesz zaimplementować semantykę dla MPlus że nie automatycznie dystrybuować >>=.(Jest to główny powód, dla którego wolę moją bibliotekę operacyjną niż wolna biblioteka.)