Control.MonadPlus.Free，无需不必要的分发

我正在尝试使用免费的 monad 构建 EDSL，用于构建像 Prolog 这样的 AND/OR 决策树，其中>>=映射到 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 节点转换为约束求解器中的具体化约束，而不会导致我希望求解器处理的替代方案数量出现组合爆炸。

In Control.MonadPlus.Free, Plus ms >>= f causes 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，后面是产生实际值的最终 monad。新的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 with Pure ()，将 capped monad 添加到列表中，并用新值替换值 monad。我意识到附加新单子的效率低下++，但我认为这和>>=将新的 monad 缝合到链的末端fmap（并且整个事情可以使用延续来重写）。

这看起来合理吗？这是否违反了单子定律（这很重要吗？），或者是否有更好的方法来使用现有的Control.Monad.Free?

你可能想看看我的操作 http://www.haskell.org/haskellwiki/Operational包，这是对免费 monad 的不同看法。

特别是，看看广度优先解析.hs https://github.com/HeinrichApfelmus/operational/tree/master/doc/examples#example-code-for-the-operational-package例子。它具有一个mplus操作使得>>= does not自动分配到它上面。这允许您以广度优先的方式实现解析器组合器。

翻译为Control.Monad.Free，重点是如果你使用函子

data F b = MZero | MPlus b b

then Free F会自动分配>>= over mplus。你必须使用函子

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

相反，如果您想实现语义MPlus不会自动分发>>=。 （这就是为什么我更喜欢我的操作库而不是免费库的主要原因。）