haskell - 是否有Codensity MonadPlus渐近优化了MonadPlus操作序列？

最近有一个question关于DList []与Codensity Free之间的关系。

这让我思考MonadPlus是否存在这种情况。 Codensity monad仅针对monadic操作而不是mplus改善渐近性能。

而且，虽然过去曾经有Control.MonadPlus.Free，但现在已经有了removed，而有了FreeT f []。而且由于没有明确的免费MonadPlus，所以我不确定如何表达对应的 improve 变体。也许像

improvePlus :: Functor f => (forall m. (MonadFree f m, MonadPlus m) => m a) -> FreeT f [] a

？

更新:我试图使用回溯 LogicT monad创建这样的monad，它似乎以类似于Codensity的方式定义:

newtype LogicT r m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r }

并且适合回溯计算，即MonadPlus。

然后我定义了lowerLogic，类似于 lowerCodensity ，如下所示:

{-# LANGUAGE RankNTypes, FlexibleInstances, FlexibleContexts, MultiParamTypeClasses,
             UndecidableInstances, DeriveFunctor #-}
import Control.Monad
import Control.Monad.Trans.Free
import Control.Monad.Logic

lowerLogic :: (MonadPlus m) => LogicT m a -> m a
lowerLogic k = runLogicT k (\x k -> mplus (return x) k) mzero

然后，在补充了对应的MonadFree实例之后

instance (Functor f, MonadFree f m) => MonadFree f (LogicT m) where
    wrap t = LogicT (\h z -> wrap (fmap (\p -> runLogicT p h z) t))

一个可以定义

improvePlus :: (Functor f, MonadPlus mr)
            => (forall m. (MonadFree f m, MonadPlus m) => m a)
            -> FreeT f mr a
improvePlus k = lowerLogic k

但是，有些事情是不对的，从我的最初实验来看，似乎k与improvePlus k是不同的。我不确定这是否是LogicT的基本限制，是否需要一个不同的，更复杂的monad，或者我是否错误地定义了lowerLogic(或其他)。

最佳答案

以下全部基于我对此的(误)理解
Matthew Pickering在他的有趣的论文中发表了
评论:From monoids to near-semirings: the essence of MonadPlus andAlternative (E. Rivas, M. Jaskelioff, T. Schrijvers)。所有结果都是他们的；所有的错误都是我的。

从免费的monoid到DList
为了建立直觉，首先考虑免费的monoid []Haskell的类别类型Hask。 []的一个问题是，如果
你有

(xs `mappend` ys) `mappend` zs = (xs ++ ys) ++ zs

然后评估需要遍历和重新遍历xs的mappend的每个左嵌套应用程序。

解决方案是使用differencelists形式的CPS:

newtype DList a = DL { unDL :: [a] -> [a] }

本文考虑了这种形式的通用形式(称为Cayley
表示形式)，其中我们不依赖于免费的monoid:

newtype Cayley m = Cayley{ unCayley :: Endo m }

带来转化

toCayley :: (Monoid m) => m -> Cayley m
toCayley m = Cayley $ Endo $ \m' -> m `mappend` m'

fromCayley :: (Monoid m) => Cayley m -> m
fromCayley (Cayley k) = appEndo k mempty

概括的两个方向

我们可以通过两种方式来概括上述构造:首先，通过
考虑的并非是Hask的mono半群，而是Hask的endofunctors;
i.e.
单子(monad)其次，通过将代数结构丰富到
近半人。
Free monads至Codensity
对于任何Haskell(endo)functor f，我们可以构造freemonad Free f，然后
左嵌套绑定(bind)会产生类似的性能问题，
使用Cayley表示的类似解决方案
Codensity 。

近半身，而不只是半身像

这是本文停止审查众所周知的概念的地方
由工作的Haskell程序员编写，并开始致力于其目标。一种
除了更简单之外，近半像环一样，因为加法和
乘法只需要是monoid。之间的联系
这是您期望的两种操作:

zero |*| a = zero
(a |+| b) |*| c = (a |*| c) |+| (b |*| c)

其中(zero, |+|)和(one, |*|)是某些
共享基础:

class NearSemiring a where
    zero :: a
    (|+|) :: a -> a -> a
    one :: a
    (|*|) :: a -> a -> a

免费的近半(超过Hask)结果如下Forest类型:

newtype Forest a = Forest [Tree a]
data Tree a = Leaf | Node a (Forest a)

instance NearSemiring (Forest a) where
    zero = Forest []
    one = Forest [Leaf]
    (Forest xs) |+| (Forest ys) = Forest (xs ++ ys)
    (Forest xs) |*| (Forest ys) = Forest (concatMap g xs)
      where
        g Leaf = ys
        g (Node a n) = [Node a (n |*| (Forest ys))]

(好东西，我们没有可交换性或逆性，
those make free representations far fromtrivial ...)

然后，本文将Cayley表示两次应用于两次
单体结构。

但是，如果我们天真地这样做，我们就会
不能得到很好的表象:我们想代表近半人，
因此必须考虑整个近半结构
帐户，而不仅仅是一个选择的类单元结构。 [...] [我们获得
内同态对半同构的半环DC(N):

newtype DC n = DC{ unDC :: Endo (Endo n) }

instance (Monoid n) => NearSemiring (DC n) where
    f |*| g = DC $ unDC f `mappend` unDC g
    one = DC mempty
    f |+| g = DC $ Endo $ \h -> appEndo (unDC f) h `mappend` h
    zero = DC $ Endo $ const mempty

(我将此处的实现从白皮书略微更改为
强调我们两次使用了Endo结构)。我们什么时候
概括地说，两层将不相同。然后纸
继续说:

注意rep不是从N到DC(N)的近半同构
因为它不会保留单元[...]
如果满足以下条件，则将保留近半计算的计算语义:
我们将值提升到表示形式，进行近半计算
在那儿，然后回到原来的近半圈。
MonadPlus几乎是半讽刺的

然后，论文继续重新制定MonadPlus类型类，以便
符合准半规规则:(mzero, mplus)是单半形的:

m `mplus` mzero = m
mzero `mplus` m = m
m1 `mplus` (m2 `mplus` m3) = (m1 `mplus` m2) `mplus` m3

并按预期方式与monad-monoid交互:

join mzero = mzero
join (m1 `mplus` m2) = join m1 `mplus` join m2

或者，使用绑定(bind):

mzero >>= _ = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)

但是，这些是而不是 existing MonadPlustypeclass from base 的规则，
列为:

mzero >>= _  =  mzero
_ >> mzero   =  mzero

本文调用满足以下条件的MonadPlus实例:
近似半定律的法则“不确定性单子(monad)”，以及
以Maybe为例，但不是
非确定性monad，因为设置MonadPlus和m1 = Just Nothing是m2 = Just(Just False)的反例。

非确定性单子(monad)的Free和Cayley表示

放在一起，一方面我们有join (m1 `mplus` m2) = join m1`mplus` join m2 -like
免费的非确定性单子(monad):

newtype FreeP f x = FreeP { unFreeP :: [FFreeP f x] }
data FFreeP f x = PureP x | ConP (f (FreeP f x))

instance (Functor f) => Functor (FreeP f) where
    fmap f x = x >>= return . f

instance (Functor f) => Monad (FreeP f) where
    return x = FreeP $ return $ PureP x
    (FreeP xs) >>= f = FreeP (xs >>= g)
      where
        g (PureP x) = unFreeP (f x)
        g (ConP x) = return $ ConP (fmap (>>= f) x)

instance (Functor f) => MonadPlus (FreeP f) where
    mzero = FreeP mzero
    FreeP xs `mplus` FreeP ys = FreeP (xs `mplus` ys)

另一方面，两个单项式的双重凯利表示
层数:

newtype (:^=>) f g x = Ran{ unRan :: forall y. (x -> f y) -> g y }
newtype (:*=>) f g x = Exp{ unExp :: forall y. (x -> y) -> (f y -> g y) }

instance Functor (g :^=> h) where
    fmap f m = Ran $ \k -> unRan m (k . f)

instance Functor (f :*=> g) where
    fmap f m = Exp $ \k -> unExp m (k . f)

newtype DCM f x = DCM {unDCM :: ((f :*=> f) :^=> (f :*=> f)) x}

instance Monad (DCM f) where
    return x = DCM $ Ran ($x)
    DCM (Ran m) >>= f = DCM $ Ran $ \g -> m $ \a -> unRan (unDCM (f a)) g

instance MonadPlus (DCM f) where
    mzero = DCM $ Ran $ \k -> Exp (const id)
    mplus m n = DCM $ Ran $ \sk -> Exp $ \f fk -> unExp (a sk) f (unExp (b sk) f fk)
      where
        DCM (Ran a) = m
        DCM (Ran b) = n

caylize :: (Monad m) => m a -> DCM m a
caylize x = DCM $ Ran $ \g -> Exp $ \h m -> x >>= \a -> unExp (g a) h m

-- I wish I called it DMC earlier...
runDCM :: (MonadPlus m) => DCM m a -> m a
runDCM m = unExp (f $ \x -> Exp $ \h m -> return (h x) `mplus` m) id mzero
  where
    DCM (Ran f) = m

本文给出了以下示例的计算结果
对于Forest表现不佳的不确定性monad:

anyOf :: (MonadPlus m) => [a] -> m a
anyOf [] = mzero
anyOf (x:xs) = anyOf xs `mplus` return x

确实，虽然

length $ unFreeP (anyOf [1..100000] :: FreeP Identity Int)

需要很长时间，Cayley转换版本

length $ unFreeP (runDCM $ anyOf [1..100000] :: FreeP Identity Int)

立即返回。

关于haskell - 是否有Codensity MonadPlus渐近优化了MonadPlus操作序列？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32252312/