Control.MonadPlus.Free без ненужного распространения

Question

Я пытаюсь использовать бесплатную монаду для создания EDSL для построения деревьев решений AND/OR, таких как Prolog, с >>=, сопоставленными с AND, и mplus, сопоставленными с OR. Я хочу описать что-то вроде A AND (B OR C) AND (D OR E), но я не хочу, чтобы дистрибутивность превращала его в (A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E). В конечном счете, я хочу преобразовать узлы AND/OR в ограниченные ограничения в решателе ограничений, не вызывая комбинаторного взрыва в числе альтернатив, с которыми я хочу, чтобы решатель имел дело.

В Control.MonadPlus.Free, Plus ms >>= f вызывает f быть применены к каждому из листьев Pure под каждой монаде в ms. Это необходимо, потому что f может дать другое значение для каждого листа Pure, которое оно заменяет.

Однако в Plus ms >> g, g может не зависеть от какой-либо из листьев ms, так распределяя его по Plus кажется ненужным.

Метод проб и ошибок, я обнаружил, что я мог бы продлить Control.MonadPlus.Free монады с новым Then конструктору:

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

Здесь новый Then конструктор имеет последовательность монад, значение которых мы игнорируем, сопровождаемая окончательная монада, которая дает фактическое значение. Новый Monad экземпляр выглядит следующим образом:

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 >> оператора «шапка» любые существующие листы, заменив Pure a с Pure(), добавляет колпачок монады к списку, и заменяет значение монады с новым. Я знаю о неэффективности добавления новой монады с ++, но я считаю, что это так же плохо, как >>=, сшивая свою новую монаду до конца цепочки с fmap (и все это можно переписать с использованием продолжений).

Это похоже на разумную вещь? Это нарушает законы монады (это имеет значение?), Или есть лучший способ использовать существующие Control.Monad.Free?

Answer 1

Возможно, вы захотите взглянуть на мой пакет operational, который по-другому берет на свободные монады.

В частности, посмотрите на пример BreadthFirstParsing.hs. Он имеет операцию mplus, так что >>= делает не автоматически распределяет по нему. Это позволяет реализовать комбинаторы парсеров в широком смысле.

Перевод на Control.Monad.Free, дело в том, что если вы используете функтор

data F b = MZero | MPlus b b 

затем Free F автоматически распространять >>= над mplus. Вы должны использовать функтор

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

вместо этого, если вы хотите реализовать семантику для MPlus, не автоматически распространять >>=.(Это основная причина, по которой я предпочитаю свою операционную библиотеку над бесплатной библиотекой.)