Safe Haskell	Safe
Language	Haskell98

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

MonadTrans C Source #
Methods lift :: Monad m => m a -> C m a #
(Monad m, Functor f) => MonadFree f (C (FreeT f m)) Source #
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 #
Functor f => MonadFree f (C (Free f)) Source #
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 (C mu) Source #
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 # fail :: String -> C mu a #
Functor (C mu) Source #
Methods fmap :: (a -> b) -> C mu a -> C mu b # (<$) :: a -> C mu b -> C mu a #
Applicative (C mu) Source #
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 #
MonadPlus mu => Alternative (C mu) Source #
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] #
MonadPlus mu => MonadPlus (C mu) Source #
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 #