Control.MonadPlus.Free没有不必要的分配 [英] Control.MonadPlus.Free without unnecessary distribution

问题描述

我试图用一个免费的monad构建一个EDSL来构建像Prolog这样的AND / OR决策树，并且>> = 映射到AND， mplus 映射到OR。我想能够描述像 A AND（B或C）AND（D OR E）之类的东西，但是我不想让distributivity把它变成<$ c （A和B和D）或（A和B和E）或（A和C和D）或（A和C和E）。最终，我想在约束求解器中将AND / OR节点转换为指定约束条件，而不会导致我想要求解器处理的多个替代方案的组合爆炸。

Control.MonadPlus.Free ， Plus ms>> = f 会导致 f 应用于 ms 中每个monad下的每个 Pure 叶子。这是必要的，因为 f 可能为每个替换的 Pure 叶子产生不同的值。

但是，在 Plus ms>> g ， g 不会受到 ms 的任何树叶的影响，在加上似乎没有必要。

通过试验和错误，我发现我可以扩展 Control.MonadPlus.Free monad用新的然后构造函数：

  data免费fa =纯a 
 |免费（f（Free f a））
 |然后[Free f（）]（Free f a）
 | Plus [Free fa] 
  

这里，新的 Then 构造函数包含一系列monad，我们忽略它的值，然后是最终的monad，得到实际值。新的 Monad 实例看起来像：

  instance Functor f => Monad（Free f）其中
 return = Pure 
 
 Pure a>> = f = fa 
 Free fa>> = f = Free $ fmap（& > = f）fa 
然后ms m>> = f =然后ms $ m> = f 
 Plus ms>> = f = Plus $ map（>>> ; = f）ms 
 
 Pure a>> mb = mb 
然后ms ma>>> mb = Then（ms ++ [ma>> =（const $ return（））]）mb 
 ma>> mb = Then [] ma>> mb 
  

>> 运算符通过用 Pure（）替换 Pure a 来覆盖任何现有叶子，将带上限的monad追加到列表中，并替换monad与新的价值。我意识到用 ++ 追加新monad的低效率，但我认为它和>>> = 使用 fmap 将它的新monad拼接到链的末尾（并且整个事物可以使用延续重写）。

这似乎是一件合理的事情吗？这违反了monad法律吗（这是否重要？），还是有更好的方式来使用现有的 Control.Monad.Free ？

解决方案

您可能想看看我的 operations 包，这是一个不同的免费monads。

特别的，看看 mplus 操作，因此>> = does not 自动分配它。这允许您以宽度优先的方式实现解析器组合器。

转换为 Control.Monad.Free ，问题是如果你使用函子

pre $ data F b = MZero | MPlus bb


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

  data F b = MZero |全部如果你想要的话，可以使用MPlus（Free fa）（Free fa）（a  - > b）
  

为 MPlus 实现不会自动分发>> = 的语义。 （这是我更喜欢使用免费库的运营库的主要原因。）

I'm trying to use a free monad to build an EDSL for constructing AND/OR decision trees like Prolog, with >>= mapped to AND, and mplus mapped to OR. I want to be able to describe something like A AND (B OR C) AND (D OR E), but I don't want distributivity to turn this into (A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E). Ultimately, I want to transform the AND/OR nodes into reified constraints in a constraint solver, without causing the combinatorial explosion in the number of alternatives that I want the solver to deal with.

In Control.MonadPlus.Free, Plus ms >>= f causes f to be applied to each of the Pure leaves under each monad in ms. This is necessary because f may yield a different value for each Pure leaf that it replaces.

However, in Plus ms >> g, g cannot be affected by any of the leaves of ms, so distributing it over the Plus seems unnecessary.

Through trial and error, I found that I could extend the Control.MonadPlus.Free monad with a new Then constructor:

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

Here, the new Then constructor holds a sequence of monads whose value we ignore, followed by the final monad that yields the actual value. The new Monad instance looks like:

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 >> operator "caps" any existing leaves by replacing Pure a with Pure (), appends the capped monad to the list, and replaces the value monad with the new one. I'm aware of the inefficiency of appending the new monad with ++, but I figure it's as bad as >>= stitching its new monad to the end of the chain with fmap (and the whole thing can be rewritten using continuations).

Does this seem like a reasonable thing to do? Does this violate the monad laws (does this matter?), or is there a better way to use the existing Control.Monad.Free?

解决方案

You may want to have a look at my operational package, which is a different take on free monads.

In particular, have a look at the BreadthFirstParsing.hs example. It features an mplus operation so that >>= does not automatically distribute over it. This allows you to implement parser combinators in a breadth-first fashion.

Translated to Control.Monad.Free, the point is that if you use the functor

data F b = MZero | MPlus b b

then Free F will automatically distribute >>= over mplus. You have to use the functor

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

instead, if you want to implement a semantics for MPlus that does not automatically distribute >>=. (This is the main reason why I prefer my operational library over the free library.)

这篇关于Control.MonadPlus.Free没有不必要的分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！