Существует ли Coadsity MonadPlus, который асимптотически оптимизирует последовательность операций MonadPlus?

Question

Существует ли Coadsity MonadPlus, который асимптотически оптимизирует последовательность операций MonadPlus?

Недавно возник вопрос о связи между DList <-> [] против Codensity <-> Free,

Это заставило меня задуматься, есть ли такая вещь для MonadPlus, Codensity Монада улучшает асимптотику только для монадических операций, а не для mplus,

Более того, пока раньше было Control.MonadPlus.Free было снято в пользу FreeT f [], А так как нет явного бесплатного MonadPlus Я не уверен, как можно выразить improve вариант. Возможно что-то вроде

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

?

Обновление: я попытался создать такую монаду, используя возврат LogicT монада, которая, кажется, определяется так, как 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 и нужна другая, более сложная монада, или просто, если я определил lowerLogic (или что-то еще) неправильно.

16

haskell monads category-theory free-monad

Источник

user1333025 27 авг '15 в 14:35

1 ответ

Решение

Другие вопросы по тегам haskell monads category-theory free-monad

user477476 01 сен '15 в 13:56 2015-09-01 13:56 · Accepted Answer · 2015-09-01 13:56

Далее все основано на моем (неправильном) понимании этой очень интересной статьи, опубликованной Мэтью Пикерингом в его комментарии: " От моноидов до почти полуколец: сущность MonadPlus и Alternative. Все результаты их; все ошибки мои.

От бесплатных моноидов до `DList`

Чтобы построить интуицию, сначала рассмотрим свободный моноид [] над категорией типов Haskell Hask, Одна проблема с [] это если у вас есть

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

затем оценка того, что требует прохождения и повторного прохождения xs за каждое левое вложенное приложение mappend,

Решение состоит в том, чтобы использовать CPS в форме списков различий:

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

В статье рассматривается общая форма этого (так называемое представление Кэли), где мы не привязаны к свободному моноиду:

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; т.е. монады; и, во-вторых, путем обогащения алгебраической структуры до полуколец.

`Free` монады в `Codensity`

Для любого Haskell (endo) функтора fмы можем построить свободную монаду Free fи у него будет аналогичная проблема производительности с лево-вложенными связями, с аналогичным решением использования представления КэлиCodensity,

Почти полукольца вместо моноидов

Здесь документ перестает рассматривать концепции, хорошо известные работающему программисту на Haskell, и начинает стремиться к своей цели. Почти полукольцо похоже на кольцо, за исключением более простого, так как сложение и умножение просто должны быть моноидами. Связь между этими двумя операциями - это то, что вы ожидаете:

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))]

(хорошо, что у нас нет коммутативности или инверсий, они делают свободные представления далеко не тривиальными...)

Затем статья дважды применяет представление Кэли к двум моноидальным структурам.

Однако, если мы делаем это наивно, мы не получим хорошего представления: мы хотим представить почти полукольцо, и поэтому должна учитываться вся структура почти полукольца, а не только одна выбранная моноидная структура. [...] [W] получаем полукольцо эндоморфизмов над эндоморфизмами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

и он взаимодействует с монадой-моноидом, как и ожидалось:

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 случаи, которые удовлетворяют подобным почти полукольцу законам "монады недетерминизма", и цитирует Maybe в качестве примера, который является MonadPlus но не монада недетерминизма, так как установка m1 = Just Nothing а также m2 = Just (Just False) контрпример к join (m1 `mplus` m2) = join m1 `mplus` join m2,

Свободное и Кэли представление недетерминированных монад

Собрав все воедино, с одной стороны, мы имеем Forest-подобная монада свободного недетерминизма:

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)

берет возраст, версия, преобразованная Кэли

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

возвращается мгновенно.

Существует ли Coadsity MonadPlus, который асимптотически оптимизирует последовательность операций MonadPlus?

1 ответ

От бесплатных моноидов до DList

Два направления обобщения

Free монады в Codensity

Почти полукольца вместо моноидов

MonadPlusпочти полукольцо

Свободное и Кэли представление недетерминированных монад

От бесплатных моноидов до `DList`

`Free` монады в `Codensity`

`MonadPlus`почти полукольцо