6

我正在尝试使用一个免费的 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

操作符通过替换为“>>封顶”任何现有叶子，将封顶的 monad 附加到列表中，并将值 monad 替换为新的。我知道将新 monad 附加到 的效率低下，但我认为它与将其新 monad 缝合到链的末尾一样糟糕（并且整个事情可以使用延续来重写）。Pure aPure ()++>>=fmap

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

4

1 回答 1

2

你可能想看看我的操作包，这是对免费单子的不同看法。

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

于 2013-12-04T13:34:08.210 回答