fusedeffects
A fast, flexible, fused effect system. https://github.com/fusedeffects/fusedeffects
LTS Haskell 14.1:  0.5.0.0 
Stackage Nightly 20190820:  0.5.0.0 
Latest on Hackage:  0.5.0.0 
Module documentation for 0.5.0.0
fusedeffects0.5.0.0@sha256:28ee6635ea8f01425d82f1fe019d215505a6a7ad6609ce950b187a0e35b28879,4215
 Control
 Control.Effect
 Control.Effect.Carrier
 Control.Effect.Cull
 Control.Effect.Cut
 Control.Effect.Error
 Control.Effect.Fail
 Control.Effect.Fresh
 Control.Effect.Interpose
 Control.Effect.Interpret
 Control.Effect.Lift
 Control.Effect.NonDet
 Control.Effect.Pure
 Control.Effect.Random
 Control.Effect.Reader
 Control.Effect.Resource
 Control.Effect.Resumable
 Control.Effect.State
 Control.Effect.Sum
 Control.Effect.Trace
 Control.Effect.Writer
 Control.Effect
A fast, flexible, fused effect system for Haskell
Overview
fusedeffects
is an effect system for Haskell emphasizing expressivity and efficiency. The former is achieved by encoding algebraic, higherorder effects, while the latter is the result of fusing effect handlers all the way through computations.
Readers already familiar with effect systems may wish to start with the usage instead.
Algebraic effects
In fusedeffects
and other systems with algebraic (or, sometimes, extensible) effects, effectful programs are split into two parts: the specification (or syntax) of the actions to be performed, and the interpretation (or semantics) given to them. Thus, a program written using the syntax of an effect can be given different meanings by using different effect handlers.
These roles are performed by the effect and carrier types, respectively. Effects are datatypes with one constructor for each action. Carriers are generally newtype
s, with a Carrier
instance specifying how an effect’s constructors should be interpreted. Each carrier handles one effect, but multiple carriers can be defined for the same effect, corresponding to different interpreters for the effect’s syntax.
Higherorder effects
Unlike most other effect systems, fusedeffects
offers higherorder (or scoped) effects in addition to firstorder algebraic effects. In a strictly firstorder algebraic effect system, operations (like local
or catchError
) which specify some action limited to a given scope must be implemented as interpreters, hardcoding their meaning in precisely the manner algebraic effects were designed to avoid. By specifying effects as higherorder functors, these operations are likewise able to be given a variety of interpretations. This means, for example, that you can introspect and redefine both the local
and ask
operations provided by the Reader
effect, rather than solely ask
(as is the case with certain formulations of algebraic effects).
As Nicolas Wu et al showed in Effect Handlers in Scope, this has implications for the expressiveness of effect systems. It also has the benefit of making effect handling more consistent, since scoped operations are just syntax which can be interpreted like any other, and are thus simpler to reason about.
Fusion
In order to maximize efficiency, fusedeffects
applies fusion laws, avoiding the construction of intermediate representations of effectful computations between effect handlers. In fact, this is applied as far as the initial construction as well: there is no representation of the computation as a free monad parameterized by some syntax type. As such, fusedeffects
avoids the overhead associated with constructing and evaluating any underlying free or freer monad.
Instead, computations are performed in a carrier type for the syntax, typically a monad wrapping further monads, via an instance of the Carrier
class. This carrier is specific to the effect handler selected, but since it isn’t described until the handler is applied, the separation between specification and interpretation is maintained. Computations are written against an abstract effectful signature, and only specialized to some concrete carrier when their effects are interpreted.
Since the interpretation of effects is written as a typeclass instance which ghc
is eager to inline, performance is excellent: approximately on par with mtl
.
Finally, since the fusion of carrier algebras occurs as a result of the selection of the carriers, it doesn’t depend on complex RULES
pragmas, making it very easy to reason about and tune.
Usage
Using builtin effects
Like other effect systems, effects are performed in a Monad
extended with operations relating to the effect. In fusedeffects
, this is done by means of a Member
constraint to require the effect’s presence in a signature, and a Carrier
constraint to relate the signature to the Monad
. For example, to use a State
effect managing a String
, one would write:
action :: (Member (State String) sig, Carrier sig m) => m ()
(Additional constraints may be necessary depending on the precise operations required, e.g. to make the Monad
methods available.)
Multiple effects can be required simply by adding their corresponding Member
constraints to the context. For example, to add a Reader
effect managing an Int
, we would write:
action :: (Member (State String) sig, Member (Reader Int) sig, Carrier sig m) => m ()
Different effects make different operations available; see the documentation for individual effects for more information about their operations. Note that we generally don’t program against an explicit list of effect components: we take the typeclassoriented approach, adding new constraints to sig
as new capabilities become necessary. If you want to name and share some predefined list of effects, it’s best to use the XConstraintKinds
extension to GHC, capturing the elements of sig
as a type synonym of kind Constraint
:
type Shared sig = ( Member (State String) sig
, Member (Reader Int) sig
, Member (Writer Graph) sig
)
myFunction :: (Shared sig, Carrier sig m) => Int > m ()
Running effects
Effects are run with effect handlers, specified as functions (generally starting with run…
) invoking some specific Carrier
instance. For example, we can run a State
computation using runState
:
example1 :: (Carrier sig m, Effect sig) => [a] > m (Int, ())
example1 list = runState 0 $ do
i < get @Int
put (i + length list)
runState
returns a tuple of both the computed value (the ()
) and the final state (the Int
), visible in the result of the returned computation. The get
function is resolved with a visible type application, due to the fact that effects can contain more than one state type (in contrast with mtl
’s MonadState
, which limits the user to a single state type).
Since this function returns a value in some carrier m
, effect handlers can be chained to run multiple effects. Here, we get the list to compute the length of from a Reader
effect:
example2 :: (Carrier sig m, Effect sig, Monad m) => m (Int, ())
example2 = runReader "hello" . runState 0 $ do
list < ask
put (length (list :: String))
(Note that the type annotation on list
is necessary to disambiguate the requested value, since otherwise all the typechecker knows is that it’s an arbitrary Foldable
. For more information, see the comparison to mtl
.)
When all effects have been handled, a computation’s final value can be extracted with run
:
example3 :: (Int, ())
example3 = run . runReader "hello" . runState 0 $ do
list < ask
put (length (list :: String))
run
is itself actually an effect handler for the Pure
effect, which has no operations and thus can only represent a final result value.
Alternatively, arbitrary Monad
s can be embedded into effectful computations using the Lift
effect. In this case, the underlying Monad
ic computation can be extracted using runM
. Here, we use the MonadIO
instance for the LiftC
carrier to lift putStrLn
into the middle of our computation:
example4 :: IO (Int, ())
example4 = runM . runReader "hello" . runState 0 $ do
list < ask
liftIO (putStrLn list)
put (length list)
(Note that we no longer need to give a type annotation for list
, since putStrLn
constrains the type for us.)
Required compiler extensions
To use effects, you’ll typically need XFlexibleContexts
.
When defining your own effects, you may need XKindSignatures
if GHC cannot correctly infer the type of your handler; see the documentation on common errors for more information about this case. XDeriveGeneric
can be used with many firstorder effects to derive default implementations of HFunctor
and Effect
.
When defining carriers, you’ll need XTypeOperators
to declare a Carrier
instance over (:+:
), XFlexibleInstances
to loosen the conditions on the instance, XMultiParamTypeClasses
since Carrier
takes two parameters, and XUndecidableInstances
to satisfy the coverage condition for this instance.
The following invocation, taken from the teletype example, should suffice for most use or construction of effects and carriers:
{# LANGUAGE DeriveFunctor, DeriveGeneric, DerivingStrategies, FlexibleContexts, FlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses, TypeOperators, UndecidableInstances #}
Defining new effects
The process of defining new effects is outlined in docs/defining_effects.md
, using the classic Teletype
effect as an example.
Project overview
This project builds a Haskell package named fusedeffects
. The library’s sources are in src
, with doctests (property tests written in documentation comments) attached to most functions. Unit tests are in test
, and library usage examples are in examples
. Further documentation can be found in docs
.
This project adheres to the Contributor Covenant code of conduct. By participating, you are expected to uphold this code.
Finally, this project is licensed under the BSD 3clause license.
Development
Development of fusedeffects
is typically done using cabal newbuild
:
cabal newbuild # build the library
cabal newtest # build and run the examples, unit tests, and doctests
The package is available on hackage, and can be used by adding it to a component’s builddepends
field in your .cabal
file.
Versioning
Though fusedeffects
is suitable for production work, it is currently in a prerelease state. Though we will attempt to comply with the Haskell Package Versioning Policy standard, we make no concrete guarantees of API stability between versions < 1.0.0.0. Once v1.0.0.0 lands, all changes will abide by the PVP MAJOR.MAJOR.MINOR.PATCH standard.
Benchmarks
To run the provided benchmark suite, use cabal newbench
. You may wish to provide the O2
compiler option to view performance under aggressive optimizations. fusedeffects
has been benchmarked against a number of other effect systems. See also @patrickt’s benchmarks.
Related work
fusedeffects
is an encoding of higherorder algebraic effects following the recipes in Effect Handlers in Scope (Nicolas Wu, Tom Schrijvers, Ralf Hinze), Monad Transformers and Modular Algebraic Effects: What Binds Them Together (Tom Schrijvers, Maciej Piróg, Nicolas Wu, Mauro Jaskelioff), and Fusion for Free—Efficient Algebraic Effect Handlers (Nicolas Wu, Tom Schrijvers).
Contributed packages
Though we aim to keep the fusedeffects
core minimal, we encourage the development of external fusedeffects
compatible libraries. If you’ve written one that you’d like to be mentioned here, get in touch!
fusedeffectslens
provides combinators to use thelens
library fluently inside effectful computations.fusedeffectsexceptions
provides handlers for exceptions thrown in theIO
monad.
Comparison to mtl
Like mtl
, fusedeffects
provides a library of monadic effects which can be given different interpretations. In mtl
this is done by defining new instances of the typeclasses encoding the actions of the effect, e.g. MonadState
. In fusedeffects
, this is done by defining new instances of the Carrier
typeclass for the effect.
Also like mtl
, fusedeffects
allows scoped operations like local
and catchError
to be given different interpretations. As with firstorder operations, mtl
achieves this with a final tagless encoding via methods, whereas fusedeffects
achieves this with an initial algebra encoding via Carrier
instances.
Unlike mtl
, effects are automatically available regardless of where they occur in the signature; in mtl
this requires instances for all valid orderings of the transformers (O(n²) of them, in general).
Also unlike mtl
, there can be more than one State
or Reader
effect in a signature. This is a tradeoff: mtl
is able to provide excellent type inference for effectful operations like get
, since the functional dependencies can resolve the state type from the monad type. On the other hand, this behaviour can be recovered in fusedeffects
using newtype
wrappers with phantom type parameters and helper functions, e.g.:
newtype Wrapper s m a = Wrapper { runWrapper :: m a }
deriving (Applicative, Functor, Monad)
instance Carrier sig m => Carrier sig (Wrapper s m) where …
getState :: (Carrier sig m, Member (State s) m) => Wrapper m s
getState = get
Indeed, Wrapper
can now be made an instance of MonadState
:
instance (Carrier sig m, Member (State s) sig, Monad m) => MTL.MonadState s (Wrapper s m) where
get = Control.Effect.State.get
put = Control.Effect.State.put
Thus, the approaches aren’t mutually exclusive; consumers are free to decide which approach makes the most sense for their situation.
Unlike fusedeffects
, mtl
provides a ContT
monad transformer; however, it’s worth noting that many behaviours possible with delimited continuations (e.g. resumable exceptions) are directly encodable as effects. Further, fusedeffects
provides a relatively large palette of these, including resumable exceptions, tracing, resource management, and others, as well as tools to define your own.
Finally, thanks to the fusion and inlining of carriers, fusedeffects
is approximately as fast as mtl
(see benchmarks).
Comparison to freersimple
Like freersimple
, fusedeffects
uses an initial encoding of library and userdefined effects as syntax which can then be given different interpretations. In freersimple
, this is done with a family of interpreter functions (which cover a variety of needs, and which can be extended for more bespoke needs), whereas in fusedeffects
this is done with Carrier
instances for newtype
s.
(Tho note that as of fusedeffects
0.3.1, it is possible to define handlers using runInterpret
in a manner analogous to freersimple
’s interpret
, with the caveat that its use of higherorder functions defeats the fusion and inlining of Carrier
instances which makes fusedeffects
so efficient.)
Unlike fusedeffects
, in freersimple
, scoped operations like catchError
and local
are implemented as interpreters, and can therefore not be given new interpretations.
Unlike freersimple
, fusedeffects
has relatively little attention paid to compiler error messaging, which can make common (compiletime) errors somewhat more confusing to diagnose. Similarly, freersimple
’s family of interpreter functions can make the job of defining new effect handlers somewhat easier than in fusedeffects
. Further, freersimple
provides many of the same effects as fusedeffects
, plus a coroutine effect, but minus resource management and random generation.
Finally, fusedeffects
has been benchmarked as faster than freersimple
.
Changes
v0.5.0.0

Derives
Generic1
instances for all nonexistentiallyquantified effect datatypes. 
Derives
Foldable
&Traversable
instances for:+:
. 
Defines
MonadFix
instances for all of the carriers. 
Reexports
run
,:+:
, andMember
fromControl.Effect.Carrier
, reducing the number of imports needed when defining new effects. 
Reexports
Carrier
,Member
, andrun
from the various effect modules, reducing the number of imports needed when using existing effects.
Backwardsincompatible changes

Replaces
runResource
with an equivalent function that usesMonadUnliftIO
to select the correct unlifting function (a lawithResource
, which is removed in favor ofrunResource
). 
Changes the signature of
eff
fromsig m (m a) > m a
tosig m a > m a
, requiring effects to holdm k
in their continuation positions instead of merelyk
. This was done in order to improve interoperability with other presentations of higherorder syntax, e.g.bound
; syntax used withbound
can now be givenHFunctor
andCarrier
instances.To upgrade effects used with previous versions, change any continuations from
k
tom k
. If no existential type variables appear in the effect, you can deriveGeneric1
, and thenceHFunctor
&Effect
instances. Otherwise, implement the required instances by hand. Since continuation positions now occur inm
,hmap
definitions will have to apply the higherorder function to these as well. 
Adds
Functor
constraints tohmap
andMonad
constraints tohandle
, allowing a greater variety of instances to be defined (e.g. for recursivelynested syntax). 
Replaces the default definitions of
hmap
andhandle
with derivations based onGeneric1
instead ofCoercible
. Therefore, firstorder effects wishing to derive these instances will requireGeneric1
instances, presumably derived usingXDeriveGeneric
. 
Moves
send
fromControl.Effect.Sum
toControl.Effect.Carrier
. Likewise removes the reexport ofsend
fromControl.Effect
. 
Deprecates
fmap'
in favour offmap
. 
Deprecates
handlePure
in favour ofhmap
.
v0.4.0.0
Backwardsincompatible changes
 Removes APIs deprecated in 0.3.0.0, including
Eff
,interpret
,ret
, and thehandle*
family of helper functions.
Other changes
 Adds the ability to derive default instances of
HFunctor
andEffect
for firstorder effects, using theXDeriveAnyClass
extension.  Adds a generic
Interpose
effect that enables arbitrary “eavesdropping” on other effects.
0.3.1.0
 Improved speed of
Reader
,State
,Writer
, andPure
effects by defining and inlining auxiliaryApplicative
methods.  Adds
runInterpret
&runInterpretState
handlers inControl.Effect.Interpret
as a convenient way to experiment with effect handlers without defining a new carrier type andCarrier
instance. Such handlers are somewhat less efficient than customCarrier
s, but allow for a smooth upgrade path when more efficiency is required.  Added
unliftiocore
as a dependency so as to provide a blessed API for unliftstyle effects and a solution to the cubiccaller problem.
0.3.0.0
Backwardsincompatible changes
 Adds
Monad
as a superclass ofCarrier
, obviating the need for a lot of constraints, andMonad
instances for all carrier types. This is a backwardsincompatible change, as any carriers users have defined now requireMonad
instances. Note that in many cases carriers can be composed out of existing carriers and monad transformers, and thus these instances can often be derived usingXGeneralizedNewtypeDeriving
. We also recommend compiling withWredundantconstraints
as many of these can now be removed.  Replaces
AltC
with a new carrier,NonDetC
, based on Ralf Hinze’s work in Deriving Backtracking Monad Transformers. This is a backwardsincompatible change.AltC
was equivalent to theListT
monad transformer, and had the same wellknown limitation to commutative monads. Therefore, the elimination ofEff
required a more durable approach.  Removes
Branch
. This is a backwardsincompatible change, but was necessitated by the difficulty of implementing correctApplicative
&Monad
instances for carriers which used it. Carriers which were employingBranch
internally should be reimplemented usingNonDetC
or a similar approach; seeCutC
andCullC
for examples.  Renames
Control.Effect.Void
,Void
, andVoidC
toControl.Effect.Pure
,Pure
, andPureC
respectively. This is a backwardsincompatible change for code mentioningVoidC
; it should be updated to referencePureC
instead.
Deprecations
Eff
andinterpret
, in favour of computing directly in the carriers. This enables the compiler to perform significant optimizations; see the benchmarks for details. Handlers can simply remove theEff
wrapping the carrier type & any use ofinterpret
. As above, we also recommend compiling withWredundantconstraints
as many of these can now be removed.ret
, in favor ofpure
orreturn
.handleEither
,handleReader
,handleState
,handleSum
, andhandleTraversable
in favour of composing carrier types directly. Carriers can be composed from other carriers andeff
defined withhandleCoercible
; and other definitions can usehandlePure
&handle
directly.
All deprecated APIs will be removed in the next release.
Other changes
 Adds a lazy
State
carrier inControl.Effect.State.Lazy
 Rewrites
CutC
using an approach related toNonDetC
, with the addition of a continuation to distinguishempty
fromcutfail
.  Rewrites
CullC
usingListC
andReaderC
.  Moves
OnceC
fromControl.Effect.NonDet
toControl.Effect.Cull
to avoid cyclic dependencies.  Adds a
runCutAll
handler forCut
effects, returning a collection of all results.
0.2.0.2
 Loosens the bounds on QuickCheck to accommodate 2.x.
0.2.0.1
 Fixes the benchmarks, and builds them in CI to avoid regressing them again.
0.2.0.0
 Adds
listen
,listens
, andcensor
operations toWriter
.  Provides explicit type parameters to
run
style functions inState
,Reader
,Writer
, andError
. This is a backwardsincompatible change for clients using these functions in combination with visible type applications.  Adds benchmarks of
WriterC
/VoidC
wrapped withEff
against their unwrapped counterparts.  Adds
Functor
,Applicative
, andMonad
instances forWriterC
.  Adds
Functor
,Applicative
, andMonad
instances forVoidC
.  Fixes a space leak with
WriterC
.  Removes the
Functor
constraint onasks
andgets
.  Adds
bracketOnError
,finally
, andonException
toResource
.  Adds
sendM
toLift
.
0.1.2.1
 Loosens the bounds on QuickCheck to accommodate 0.12.
0.1.2.0
 Adds support for ghc 8.6.2, courtesy of @jkachmar.
 Adds a
Cut
effect which adds committed choice to nondeterminism.  Adds a
Cull
effect which adds pruning to nondeterminism.  Adds an example of using
NonDet
,Cut
, and a character parser effect to define parsers.  Fixes the table of contents links in the README.
0.1.1.0
 Adds a
runNonDetOnce
handler which terminates immediately upon finding a solution.
0.1.0.0
Initial release.