Control.MonadPlus.Free没有不必要的分发

Question

我正在尝试使用一个免费的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导致f应用于Pure每个monad下的每个叶子ms.这是必要的,因为它f可能为Pure它所替换的每个叶子产生不同的值.

但是,在Plus ms >> g,g不能受任何叶子的影响ms,所以分配它Plus似乎是不必要的.

通过反复试验,我发现我可以Control.MonadPlus.Free使用新的Then构造函数扩展monad :

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

该>>运营商"帽"替换任何现有的叶Pure a用Pure (),追加封顶单子到列表中,并替换为新的一个值单子.我知道附加新monad的效率低下++,但我认为它与将新monad >>=拼接到链的末尾一样糟糕fmap(并且整个事情可以使用continuation重写).

这看起来像是一件合理的事吗？这是否违反了monad法律(这有关系吗？),还是有更好的方法来使用现有的Control.Monad.Free？

Answer 1

您可能想看看我的操作包，这是对免费 monad 的不同看法。

特别是，请查看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相反，如果您想实现不会自动分发的语义>>=。（这就是为什么我更喜欢我的操作库而不是免费库的主要原因。）