Safe Haskell	Safe-Inferred
Language	Haskell2010

Control.Monad.Free.Improve

Description

Naive Free monads suffer from a quadratic complexity, as explained in

Janis Voigtlander, Asymptotic Improvement of Computations over Free Monads, MPC'08

The solution is to redefine the Free datatype in CPS, similar to what is done in difference lists to solve the problem on quadratic append for lists.

Documentation

newtype C (mu :: Type -> Type) a Source #

Constructors

C (forall b. (a -> mu b) -> mu b)

Instances

Instances details

MonadTrans C Source #
Instance details Defined in Control.Monad.Free.Improve Methods lift :: Monad m => m a -> C m a
Functor f => MonadFree f (C (Free f)) Source #
Instance details Defined in Control.Monad.Free.Improve Methods free :: C (Free f) a -> C (Free f) (Either a (f (C (Free f) a))) Source # wrap :: f (C (Free f) a) -> C (Free f) a Source #
(Monad m, Functor f) => MonadFree f (C (FreeT f m)) Source #
Instance details Defined in Control.Monad.Free.Improve Methods free :: C (FreeT f m) a -> C (FreeT f m) (Either a (f (C (FreeT f m) a))) Source # wrap :: f (C (FreeT f m) a) -> C (FreeT f m) a Source #
MonadPlus mu => Alternative (C mu) Source #
Instance details Defined in Control.Monad.Free.Improve Methods empty :: C mu a (<\|>) :: C mu a -> C mu a -> C mu a some :: C mu a -> C mu [a] many :: C mu a -> C mu [a]
Applicative (C mu) Source #
Instance details Defined in Control.Monad.Free.Improve Methods pure :: a -> C mu a (<>) :: C mu (a -> b) -> C mu a -> C mu b liftA2 :: (a -> b -> c) -> C mu a -> C mu b -> C mu c (>) :: C mu a -> C mu b -> C mu b (<*) :: C mu a -> C mu b -> C mu a
Functor (C mu) Source #
Instance details Defined in Control.Monad.Free.Improve Methods fmap :: (a -> b) -> C mu a -> C mu b # (<$) :: a -> C mu b -> C mu a #
Monad (C mu) Source #
Instance details Defined in Control.Monad.Free.Improve Methods (>>=) :: C mu a -> (a -> C mu b) -> C mu b # (>>) :: C mu a -> C mu b -> C mu b # return :: a -> C mu a #
MonadPlus mu => MonadPlus (C mu) Source #
Instance details Defined in Control.Monad.Free.Improve Methods mzero :: C mu a # mplus :: C mu a -> C mu a -> C mu a #

rep :: Monad mu => mu a -> C mu a Source #

improve :: Monad mu => C mu a -> mu a Source #