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的低效率,但我认为它和>>> = $一样糟糕c $ c>使用
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屋!