haskell - 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 节点转换为约束求解器中的具体约束，而不会导致我希望求解器处理的备选方案数量的组合爆炸。

在 Control.MonadPlus.Free , Plus ms >>= f原因 f应用于每个 Pure在 ms 中的每个 monad 下离开.这是必要的，因为 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 替换为新的值。我知道用 ++ 附加新的 monad 效率低下。 , 但我认为它和 >>= 一样糟糕用 fmap 将它的新 monad 缝合到链的末端(并且可以使用延续来重写整个事情)。

这似乎是一件合理的事情吗？这是否违反单子(monad)定律(这有关系吗？)，还是有更好的方法来使用现有的 Control.Monad.Free ?

Answer 1

你可能想看看我的operational包，这是对免费单子(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 的语义不会自动分发 >>= . (这就是为什么我更喜欢我的操作库而不是免费库的主要原因。)