gpt4 book ai didi

haskell - 是否存在渐近优化一系列 MonadPlus 操作的 Codensity MonadPlus?

转载 作者:行者123 更新时间:2023-12-03 23:50:51 28 4
gpt4 key购买 nike

最近有一个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) .所有的结果都是他们的;所有的错误都是我的。

从自由幺半群到 DList
为了建立直觉,首先考虑自由幺半群[]超过
Haskell 类型的类别 Hask . [] 的一个问题是如果
你有

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

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

解决方案是使用 differencelists 形式的 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.
单子(monad);其次,通过将代数结构丰富为
近半明。
Free单子(monad)到 Codensity
对于任何 Haskell (endo)functor f ,我们可以构造 freemonad Free f , 和
左嵌套绑定(bind)会有类似的性能问题,
使用 Cayley 表示的类似解决方案
Codensity .

Near-semirings 而不仅仅是幺半群

这是本文停止审查众所周知的概念的地方
由正在工作的 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

免费的近乎半透明(超过 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 表示,
单面结构。

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

或者,使用绑定(bind):
mzero >>= _ = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)

但是,这些是 不是 existing MonadPlus typeclass from base 的规则,
其中列出为:
mzero >>= _  =  mzero
_ >> mzero = mzero

论文调用 MonadPlus满足的实例
近乎半透明的定律“非确定性单子(monad)”,以及
引用 MaybeMonadPlus 为例但不是一个
非确定性单子(monad),自设置 m1 = Just Nothingm2 = Just
(Just False)
join (m1 `mplus` m2) = join m1
`mplus` join m2
的反例.

非确定性单子(monad)的自由和凯莱表示

把所有东西放在一起,一方面我们有 Forest -喜欢
自由的非确定性单子(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

本文给出了以下计算示例
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)

立即返回。

关于haskell - 是否存在渐近优化一系列 MonadPlus 操作的 Codensity MonadPlus?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32252312/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com