Control.MonadPlus.Free沒有不必要的分配

我試圖使用免費的monad來構建一個EDSL來構建AND/OR決策樹，如Prolog，其中>>=映射到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沒有不必要的分配

在Control.MonadPlus.Free，Plus ms >>= f導致f每個單子下ms被施加到每個Pure樹葉。這是必要的，因爲f可能爲它替換的每個Pure葉產生不同的值。

然而，在Plus ms >> g，g不能由任何ms葉子的影響，所以它分佈在Plus似乎沒有必要。

經過反覆試驗，我發現我可以用一個新Then構造擴展Control.MonadPlus.Free單子：

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

在這裏，新Then構造持有的單子，其價值我們忽略的一個序列，然後是最終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()更換Pure a任何現有的樹葉，追加封頂單子到列表中，並替換爲新的一個值單子。我意識到追加新單元的效率不高++，但我認爲它與>>=一樣糟糕，將其新單元與fmap拼接在一起（並且整個事情可以使用延續重寫）。

這似乎是一個合理的事情嗎？這是否違反了monad法律（這是否重要？），還是有更好的方法來使用現有的Control.Monad.Free？

來源

2013-10-04 pat

你可能想看看我的operational包，這是一個不同的自由monads。

特別是，看看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-04 13:34:08

Control.MonadPlus.Free沒有不必要的分配

回答

相關問題