control-monad-free-0.6.2: Free monads and monad transformers
Safe HaskellSafe-Inferred
LanguageHaskell2010

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 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 #