是否存在渐近优化一系列 MonadPlus 操作的代码密度 MonadPlus？
Is there a Codensity MonadPlus that asymptotically optimizes a sequence of MonadPlus operations?
最近有一个 关于 DList <-> [] 与 Codensity <-> Free.[=41= 之间的关系]
这让我想到MonadPlus是否有这样的事情。 Codensity monad 仅提高 monadic 操作的渐近性能，而不是 mplus.
此外，虽然曾经有 Control.MonadPlus.Free，但现在已经是 in favor of FreeT f []. And since there is no explicit free MonadPlus, I'm not sure how one would express a corresponding 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（或其他东西）。
以下都是基于我对这个非常（错误）的理解
马修皮克林在他的
评论：从幺半群到近半环：MonadPlus 的本质和
备选方案（E. Rivas、M. Jaskelioff、T. Schrijvers）。所有的结果都是他们的；所有的错误都是我的。
从自由幺半群到 DList
为了建立直觉，首先考虑自由幺半群 []
Haskell 类型的类别 Hask。 [] 的一个问题是如果
你有
(xs `mappend` ys) `mappend` zs = (xs ++ ys) ++ zs
然后评估需要遍历和重新遍历xs
mappend.
的每个左嵌套应用程序
解决办法是用形式的CPS区别
列表:
newtype DList a = DL { unDL :: [a] -> [a] }
这篇论文考虑了这个的通用形式（称为 Cayley
表示），我们不受自由幺半群的约束：
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，但超过 Hask 的内函子；
i.e.
单子;其次，通过将代数结构丰富为
近半环。
Free 单子到 Codensity
对于任何 Haskell (endo)functor f，我们可以构建 free
monad Free f 和
它将具有与左嵌套绑定类似的性能问题，
与使用 Cayley 表示的类似解决方案
Codensity.
近半环而不只是幺半群
这是本文停止审查众所周知的概念的地方
由正在工作的 Haskell 程序员，并开始确定其目标。一种
near-semiring 就像一个环，除了更简单，因为加法和
乘法只需要是幺半群。之间的联系
这两个操作就是你所期望的：
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
免费的near-semiring（超过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))]
（幸好我们没有交换律或逆律，
那些做自由交涉的远非
琐碎...)
然后，论文两次应用凯莱表示，对两个
单体结构。
However, if we do this naively, we do
not get a good representation: we want to represent a near-semiring,
and therefore the whole near-semiring structure must be taken into
account and not just one chosen monoid structure. [...] [W]e obtain
the semiring of endomorphisms over endomorphisms 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 结构两次）。我们什么时候
概括这一点，这两个层将不相同。纸然后
继续说：
Note that rep is not a near-semiring homomorphism from N into DC(N)
as it does not preserve the unit [...] Nevertheless, [...] the
semantics of a computation over a near-semiring will be preserved if
we lift values to the representation, do the near-semiring computation
there, and then go back to the original near-semiring.
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
或者，使用绑定：
mzero >>= _ = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)
但是，这些 不是 现有 MonadPlus 的规则
类型类来自
base,
列为：
mzero >>= _ = mzero
_ >> mzero = mzero
论文调用 MonadPlus 个满足
near-semiring-like 法则 "nondeterminism monads"，以及
引用 Maybe 作为 MonadPlus 但不是
非确定性 monad，因为设置 m1 = Just Nothing 和 m2 = Just
(Just False) 是 join (m1 `mplus` m2) = join m1
`mplus` join m2.
的反例
非确定性单子的自由和凯莱表示
把所有东西放在一起，一方面我们有 Forest-like
免费的非确定性单子：
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
该论文给出了以下计算示例 运行
FreeP:
表现不佳的非确定性 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)
returns立即。
最近有一个 这让我想到 此外，虽然曾经有 ? 更新： 我试图使用回溯 适合回溯计算，即 然后我定义了 然后，补充相应的 可以定义 但是，它有些不对劲，因为从我最初的实验来看，对于某些示例，DList <-> [] 与 Codensity <-> Free.[=41= 之间的关系]
MonadPlus是否有这样的事情。 Codensity monad 仅提高 monadic 操作的渐近性能，而不是 mplus.Control.MonadPlus.Free，但现在已经是 FreeT f []. And since there is no explicit free MonadPlus, I'm not sure how one would express a corresponding 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（或其他东西）。
以下都是基于我对这个非常（错误）的理解 马修皮克林在他的 评论：从幺半群到近半环：MonadPlus 的本质和 备选方案（E. Rivas、M. Jaskelioff、T. Schrijvers）。所有的结果都是他们的；所有的错误都是我的。
从自由幺半群到 DList
为了建立直觉，首先考虑自由幺半群 []
Haskell 类型的类别 Hask。 [] 的一个问题是如果
你有
(xs `mappend` ys) `mappend` zs = (xs ++ ys) ++ zs
然后评估需要遍历和重新遍历xs
mappend.
解决办法是用形式的CPS区别 列表:
newtype DList a = DL { unDL :: [a] -> [a] }
这篇论文考虑了这个的通用形式（称为 Cayley 表示），我们不受自由幺半群的约束：
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，但超过 Hask 的内函子；
i.e.
单子;其次，通过将代数结构丰富为
近半环。
Free 单子到 Codensity
对于任何 Haskell (endo)functor f，我们可以构建 free
monad Free f 和
它将具有与左嵌套绑定类似的性能问题，
与使用 Cayley 表示的类似解决方案
Codensity.
近半环而不只是幺半群
这是本文停止审查众所周知的概念的地方 由正在工作的 Haskell 程序员，并开始确定其目标。一种 near-semiring 就像一个环，除了更简单，因为加法和 乘法只需要是幺半群。之间的联系 这两个操作就是你所期望的：
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
免费的near-semiring（超过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))]
（幸好我们没有交换律或逆律， 那些做自由交涉的远非 琐碎...)
然后，论文两次应用凯莱表示，对两个 单体结构。
However, if we do this naively, we do not get a good representation: we want to represent a near-semiring, and therefore the whole near-semiring structure must be taken into account and not just one chosen monoid structure. [...] [W]e obtain the semiring of endomorphisms over endomorphisms
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 结构两次）。我们什么时候
概括这一点，这两个层将不相同。纸然后
继续说：
Note that
repis not a near-semiring homomorphism fromNintoDC(N)as it does not preserve the unit [...] Nevertheless, [...] the semantics of a computation over a near-semiring will be preserved if we lift values to the representation, do the near-semiring computation there, and then go back to the original near-semiring.
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
或者，使用绑定：
mzero >>= _ = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)
但是，这些 不是 现有 MonadPlus 的规则
类型类来自
base,
列为：
mzero >>= _ = mzero
_ >> mzero = mzero
论文调用 MonadPlus 个满足
near-semiring-like 法则 "nondeterminism monads"，以及
引用 Maybe 作为 MonadPlus 但不是
非确定性 monad，因为设置 m1 = Just Nothing 和 m2 = Just
(Just False) 是 join (m1 `mplus` m2) = join m1
`mplus` join m2.
非确定性单子的自由和凯莱表示
把所有东西放在一起，一方面我们有 Forest-like
免费的非确定性单子：
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
该论文给出了以下计算示例 运行
FreeP:
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)
returns立即。