Недавно был вопрос о связи между 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
monad, которая кажется быть определена аналогично Codensity
:
newtype LogicT r m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r }
и подходит для вычислений обратного слежения, то есть MonadPlus
.
Затем я определил lowerLogic
, аналогичный lowerCodensity
как followd:
{-# 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
(или что-то еще).