What is an effect? Link to heading

Effects are the parts of computations outside of what is handled by the input/output of a function or construct (class/struct/etc.). Take a function like the following:

def backwards[A, B](a: A, b: B) = (b, a)

This doesn’t have any effects 1, it just takes two arguments and returns a tuple of them backwards.

Now if we look at this function:

public boolean save(User user) {
    return db.save(user);
}

There are several effects happening here, and most of them are untyped/untracked

  • save is immediately evaluating and executing. This means we can’t easily compose the effect of saving the user, there’s no effect being tracked by the type system that is returned that allows composition with other effects.
  • db.save could throw an exception (say if the db is not initialized), this is untyped and implicit. While we can make it explicit with a try/catch, the compiler isn’t going to help us at all in locating where we need to do this 2.
  • db is in scope despite not being passed into the function. while this is an effect it’s not usually untyped/implicit, rather it’d likely be defined in the enclosing scope explicitly, so not as bad as the other effects. It being an effect means general mechanisms for effect handling should be able to make db available through other mechanisms, which we’ll see later in this post.
  • user or db could be null. This is an implicit, untyped effect in Java. Some languages track null at the type level, and others use more general mechanisms for handling the effect.

Often times these untyped effects are also referred to as “side effects”, as they happen “on the side” of what the function says it’ll do.

This article will cover different ways of tracking these effects at the type level, and we’ll showcase alternatives to the above save function with typed/tracked effects. We’ll also create a more advanced function, transform, that:

simultaneously executes these two tasks

  1. fetch a user by id
  2. fetch a set of pending changes for the user id

then applies those changes to the user, deletes the existing user and pending changes, and then saves the new user.

For the rest of this post, the save and transform examples will have line numbers, while other code snippets will not.

Untyped Effect Wrapping Link to heading

Untyped effects will usually be the most familiar to non-FP programmers, effects are untracked by the type system and exist solely at runtime. The last section went into an example of untyped effects with the public void save method.

When you consider that an effect is part of a computation that happens outside of the input/output of a function or construct, you might realize that you can wrap or lift these untyped parts into typed parts. We can:

  • use Either[Failure, Success] to denote possible failures instead of exceptions
  • have lazy computation with () -> A
  • have suspension with CompletableFuture
  • replace nullables with Optionals
  • explicitly pass parameters instead of relying on some larger scope

Applying all these ideas transforms our original Java save function into:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public Supplier<CompletableFuture<Either<MyError, Optional<Boolean>>>> save(
    User user, Database db
) {
    return () -> {
        try {
            if (db == null || user == null) {
                return CompletableFuture.completedFuture(
                    Either.right(Optional.empty()));
            } else {
                return db.save(user).get().thenApply(either -> 
                    either.map(Optional::of));
            }
        } catch (Exception e) {
            return CompletableFuture.completedFuture(
                Either.left(new MyError(e)));
        }
    };
}

You might imagine this kind of function is where we’re incurring the largest costs, but actually composing several of these is much more problematic. There’s no general mechanism in Java for composition of single effects, nor is the type system expressive enough to allow composition of n effects generically; we have to create a new combinator for every effect combination we want to represent

For this reason, the transform function is quite tedious compared to later examples:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public Supplier<CompletableFuture<Either<MyError, Boolean>>> transform(
    UserRepository userRepo,
    ChangeRepository changeRepo,
    int userId
) {
    return () -> {
        try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
            var oldUserThread = scope.fork(() -> 
                userRepo.fetch(userId).get());
            var changesThread = scope.fork(() -> 
                changeRepo.pendingUserChanges(userId).get());
            scope.join();

            var userEitherFuture = oldUserThread.get()
                .thenApply(eitherOpt -> eitherOpt.flatMap(opt ->
                    optToEither(opt, new MyError("user missing"))));

            return
                bindEff(() -> userEitherFuture, oldUser ->
                bindEff(() -> changesThread.get(), changes -> {
                    var newUser = changes.stream().reduce(
                        Function.identity(), Function::andThen
                    ).apply(oldUser);

                    return
                        bindEff(userRepo.delete(userId), r1 ->
                        bindEff(changeRepo.deletePendingFor(userId), r2 ->
                        bindEff(userRepo.save(newUser), r3 ->
                            CompletableFuture.completedFuture(
                                Either.right(r1 && r2 && r3))
                        )));
                }));
        } catch (InterruptedException e) {
            return CompletableFuture.completedFuture(
                Either.left(new MyError(e)));
        }
    };
}

private <E, S> Either<E, S> optToEither(Optional<S> opt, E ifEmpty) {
    return opt.map(Either::<E, S>right).orElse(Either.left(ifEmpty));
}

private <E, S, U> CompletableFuture<Either<E, U>> bindEff(
    Supplier<CompletableFuture<Either<E, S>>> f1,
    Function<S, CompletableFuture<Either<E, U>>> f2
) {
    return f1.get().thenCompose(e -> e.fold(
        ex -> CompletableFuture.completedFuture(Either.left(ex)),
        f2
    ));
}

Let’s take this piece-by-piece.

First we create a scope and fork two threads off of it, meaning those two threads will execute concurrently. scope.join waits for both of them to complete.

try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
    var oldUserThread = scope.fork(() -> 
        userRepo.fetch(userId).get());
    var changesThread = scope.fork(() -> 
        changeRepo.pendingFor(userId).get());
    scope.join();

    (...)

we handle the empty case for the oldUserThread:

var userEitherFuture = oldUserThread.get()
    .thenApply(eitherOpt -> eitherOpt.flatMap(opt ->
        optToEither(opt, new MyError("user missing"))));

and most of the rest of the function is using the bindEff combinator to compose CompletableFuture<Either<E, S>>s. bindEff has an incredibly similar signature to flatMap, where flatMap is usually of this shape:

def flatMap[F[_], A, B](fa: F[A])(fn: A => F[B])

flatMap being the core computation of Monads, which we’ll get into later. Having the language allow easy sequencing of monads would greatly improve this code.

Despite using the newest Java release at the time of writing (23) with the structured concurrency preview, async programming is still far behind what other languages offer. Instead of simply having a combinator like <&> (which we will see later), we instead need to create a structured scope, fork each computation, join the scope, and then retrieve the computed result manually afterwards.

Reified Effects Link to heading

Some languages track specific effects, but don’t have a general mechanism for effect handling. This means handling each kind of effect has different syntax/semantics, and composing them is generally impossible (so every effect has to be unwrapped with syntax specific to it).

Some examples:

  • Java checked exceptions
  • Kotlin suspend, null tracking
  • Swift async/await, throws, nil tracking, arguably state management

Other kinds of effects 3 are left as untyped, because the languages aren’t setup to specifically handle these effects/monads.

We’ll showcase reified effects with Swift, because it leans heavily on these, more-so than most languages in its class.

To start, let’s remake the save function

1
2
3
func save(user: User, db: Database) async throws(MyError) -> Bool {
    try await db.save(user: user)
}

note: at this point, save is entirely redundant, as we’re not lifting any untyped components into new type wrappers like in the Java

The effects above are typed, without having to engage in as much manual wrapping as the Java:

  • we don’t have to handle nulls because the lack of ? in a type means it’s non-nullable
  • async allows easy suspension of the computation (semantically similar to Java’s CompletableFuture + Supplier)
  • throws(MyError) means the computation could also throw a MyError instead of return a Bool

Similarly, the transform function is much more clear than the Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func transform(
    userRepo: UserRepository, 
    changeRepo: ChangeRepository, 
    userId: Int
) async throws(MyError) -> Bool {
    async let oldUserOptAsync = userRepo.fetch(byId: userId)
    async let changesAsync = changeRepo.pendingFor(byId: userId)

    guard let oldUser = try await oldUserOptAsync else { 
        throw MyError(message: "user missing") 
    }
    let changes = try await changesAsync
    let newUser = changes.reduce(oldUser) { user, change in change(user) }

    let r1 = try await userRepo.delete(byId: userId)
    let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
    let r3 = try await userRepo.save(user: newUser)

    return r1 && r2 && r3
} 
  • async let is a much more clear mechanism for allowing concurrent computations than Java’s structured concurrency,
  • let rN = try await <expr> flattens the unwrapping in a clear way
  • guard let v = <expr> else { <expr2> } allows easy management of a nilable value

Monads Link to heading

Monads are a more generic mechanism for effect handling as it allows libraries or private repositorities to define and handle their own effects on top of or in addition to more widely used ones, though monads of one type do not compose with monads of another type. We’ll get into a way around this, monad transformers, a bit later.

Monad is trivial to define:

trait Monad[F[_]] extends Functor[F]: // Functor provides `map`
    def pure[A](a: A): F[A]
    def flatMap[A, B](fa: F[A])(fn: A => F[B]): F[B]

syntax is generally provided to allow fa.flatMap(fn) instead of someMonad.flatMap(fa)(fn), though this would also be easy to define yourself:

extension [F[_], A](fa: F[A])
    def flatMap[B](fn: A => F[B])(using m: Monad[F]): F[B] =
        m.flatMap(fa)(fn)

Some languages lack the ability to express monads, as you need higher kinded types to define the abstraction. If you’re unfamiliar with HKTs, check out my article on them.

We’ll commonly interface with monadic types through for/monad comprehensions, so instead of something like this:

m1.flatMap: a1 =>
    m2.flatMap: a2 =>
        m3.map: a3 =>
            a1 + a2 + a3

we’d instead write:

for
    a1 <- m1
    a2 <- m2
    a3 <- m3
yield a1 + a2 + a3

Now onto the save/transform examples:

1
def save(user: User, db: Database) = db.save(user)

like the Swift, this save function is entirely redundant now

And our transform function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def transform(
    userRepo: UserRepository,
    changeRepo: ChangeRepository,
    userId: Int
): IO[Either[MyError, Boolean]] = for
    userEither = userRepo.fetch(userId).map(_.flatMap: opt => 
        opt.toRight(MyError("user missing")))

    newUserEither <- IO.both(
        userEither,
        changeRepo.pendingUserChanges(userId)
    ).map((oldUserEither, changesEither) => for
        oldUser <- oldUserEither
        changes <- changesEither
    yield changes.foldLeft(oldUser)((user, change) => change(user)))

    r1E <- userRepo.delete(userId)
    r2E <- changeRepo.deletePendingUserChanges(userId)
    r3E <- newUserEither.flatTraverse(userRepo.save)
yield for
    r1 <- r1E
    r2 <- r2E
    r3 <- r3E
yield r1 && r2 && r3

while this code is notably shorter than the Java code, we still see some of the same complexity because monads don’t compose, though we have better combinators (and for comps) for dealing with some of that complexity, which is why this is half the Java’s length.

Also worth note, this is worse than the Swift in a number of ways:

  • unwrapping r1/r2/r3 is more complex (requiring first unwrapping IO then later Either).
  • composition of multiple effects requires combinators to align the types. When we create a value like newUserEither, assigning it to a binding requires managing the effects explicitly.

Luckily this lack of composability was known from the inception of monads, and different approaches can be taken to rectify this.

Monad Transformers Link to heading

Monad Transformers 4 are probably the most common solution to the composability problem with monads. A monad transformer takes two monads and combines them into a single monad. So if you take a computation like IO[Either[MyError, A]] and pass it into EitherT, you get EitherT[IO, MyError, A], meaning flatMaping on it will give you an A instead of Either[MyError, A]. This vastly simplifies its usage in monad comprehensions/for comps.

Our save/transform examples using the EitherT monad transformer:

1
def save(user: User, db: Database) = EitherT(db.save(user))

and

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def transform(
    userRepo: UserRepository,
    changeRepo: ChangeRepository,
    userId: Int
): EitherT[IO, MyError, Boolean] = for
    oldUserOptAsync <- EitherT.liftF(userRepo.fetch(userId).start)
    changesAsync <- EitherT.liftF(changeRepo.pendingFor(userId).start)

    oldUser <- EitherT(oldUserOptAsync.joinWithNever).flatMap:
        EitherT.fromOption(_, MyError("user missing"))
    changes <- EitherT(changesAsync.joinWithNever)
    newUser = changes.foldLeft(oldUser)((user, change) => change(user))

    r1 <- EitherT(userRepo.delete(userId))
    r2 <- EitherT(changeRepo.deletePendingUserChanges(userId))
    r3 <- EitherT(userRepo.save(newUser))
yield r1 && r2 && r3

liftF is a mechanism to convert F[A] into EitherT[F, Nothing, A]. Nothing as the error type allows easy composition with other EitherTs, as Nothing | A =:= A. It’s a bottom type with no inhabitants.

EitherT’s apply (what’s called with the EitherT(something) syntax) converts an F[Either[E, A]] into EitherT[F, E, A].

There are other combinators, like fromOption, fromEither, etc. that are used to convert various values into EitherT.

This transform is extremely similar structurally to the Swift. I’ve used all the same binding names to highlight the similarities, and the expressions do roughly the same thing. For direct comparison:

async let oldUserOptAsync = userRepo.fetch(byId: userId)
async let changesAsync = changeRepo.pendingFor(byId: userId)

guard let oldUser = try await oldUserOptAsync else { 
    throw MyError(message: "user missing") 
}
let changes = try await changesAsync
let newUser = changes.reduce(oldUser) { user, change in change(user) }

let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)

vs

oldUserOptAsync <- EitherT.liftF(userRepo.fetch(userId).start)
changesAsync <- EitherT.liftF(changeRepo.pendingFor(userId).start)

oldUser <- EitherT(oldUserOptAsync.joinWithNever).flatMap:
    EitherT.fromOption(_, MyError("user missing"))
changes <- EitherT(changesAsync.joinWithNever)
newUser = changes.foldLeft(oldUser)((user, change) => change(user))

r1 <- EitherT(userRepo.delete(userId))
r2 <- EitherT(changeRepo.deletePendingUserChanges(userId))
r3 <- EitherT(userRepo.save(newUser))

Algebraic Effects Link to heading

Algebraic effects (AE) are another generic mechanism for effect handling, and don’t require language-level support for each effect encoding. They are much more composable than standalone monads, or even mtl monads. Algebraic effects can be introduced as a language feature 5 or as a library 6 built on top of monads if the language’s type system is expressive enough (Haskell and Scala 3 hit this bar).

We’ll use kyo in Scala to demonstrate AEs. Our save function using kyo:

1
2
def save(user: User, db: Database): Boolean < (Async & Abort[MyError]) =
    db.save(user)

Here, save returns a Boolean with the tracked effects Async and Abort[MyError].

Abort is similar to throws, though Abort[Absent] is used to represent empty values, and Abort[Nothing] for panics. All other Aborts can be viewed as isomorphic to throws(E) or Either[E, ?].

Similar to the Reader monad, we have an Env effect that allows us to require a dependency. Env is a good alternative to DI, as it has compile-time safe resolution of dependencies, and has very lightweight syntax.

For our save function, if we want to require a Database, we can do it like this:

1
2
3
def save(user: User): Boolean < (Async & Abort[MyError] & Env[Database]) = for
    db <- Env.get[Database]
yield db.save(user)

with the use of type inference and map this can be made much shorter:

1
def save(user: User) = Env.get[Database].map(_.save(user))

Imagine now that we have a cacheIfMissing function we want to call here, if it’s typed as Boolean < (Async & Env[Redis]), we could use it like so:

def saveThenMaybeCache(user: User) = for
    db <- Env.get[Database]
    r1 <- db.save(user)
    r2 <- cacheIfMissing(user)
yield r1 && r2

when you check the type of saveThenMaybeCache, you’ll find it’s:

Boolean < (Async & Abort[MyError] & Env[Database] & Env[Redis])
  • multiple computations can require some effect (like Async), but it’ll only be required once in the resulting effect type
  • in the vast majority of cases, sequencing a new computation (like we did with cacheIfMissing) will seamlessly add the new effects to the current expression (e.g the for comp) with intersection types (&). In the above, an Env[Redis] is required, so that requirement is propagated up.

Now, finally onto the transform function in kyo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def transform(userId: Int) = for
    userRepo   <- Env.get[UserRepository]
    changeRepo <- Env.get[ChangeRepository]

    fetchUser = userRepo.fetch(userId)
        .emptyAbortToFailure(MyError("user missing"))

    (oldUser, changes) <- fetchUser <&> changeRepo.pendingFor(userId)
    newUser = changes.foldLeft(oldUser)((user, change) => change(user))

    r1 <- userRepo.delete(userId)
    r2 <- changeRepo.deletePendingUserChanges(userId)
    r3 <- userRepo.save(newUser)
yield r1 && r2 && r3

This is the most composable of all the transform functions presented, for the same reason it’s also the most concise and (I’d argue) the most clear. Some notes about it:

  1. Env.get provides us with an alternative to dependency injection that is compile-time safe and provided for entirely at the type level. The return type of transform is the sum of all the effects used within the function, so unlike something like the ReaderT monad transformer, it doesn’t add extra complexity to other expressions within the function. It’s all the safety of normal dependencies with the convenience of a DI framework.
  2. While we could use Async.run/fork to mimic the Swift’s async let and the mtl Scala’s EitherT.liftF(someIO.start), we can also make use of the Async.parallel/<&>, which are very similar to the standalone monadic Scala IO.both, meaning instead of:
async let aAsync = fetchA(v)
async let bAsync = fetchB(v)

let a = await aAsync
let b = await bAsync

we can:

(a,b) <- fetchA(v) <&> fetchB(v)

though if we prefer we can still structure it the same as the Swift/mtl Scala:

aAsync <- fetchA(v).fork
bAsync <- fetchB(v).fork

a <- aAsync.get
b <- bAsync.get
  1. since the effects compose, we don’t need a bunch of disparite syntax to manually combine the effects like you do with Swift, nor to pass it into a monad transformer to flatten it like in the mtl Scala. The r1/r2/r3` code showcases this clearly:
r1 <- userRepo.delete(userId)
r2 <- changeRepo.deletePendingUserChanges(userId)
r3 <- userRepo.save(newUser)

vs

let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)

These are representing the same effects, save’s return type in scala is Boolean < (Async & Abort[MyError]), while in Swift it’s async throws(MyError) -> Boolean.

To highlight AE composition, imagine we add an r4 that has the same return type as r3, except we want to represent a missing value (null/nil/none/etc.), and then propagate this missing value upwards. In the Swift we’d end up with:

let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)
guard let r4 = try await userRepo.someFn(userId) else { return nil }
return r1 && r2 && r3 && r4

In the mtl Scala we’d end up with:

    r1 <- EitherT(userRepo.delete(userId))
    r2 <- EitherT(changeRepo.deletePendingUserChanges(userId))
    r3 <- EitherT(userRepo.save(newUser))
    r4Opt <- EitherT(userRepo.someFn(userId))
yield r4Opt.map(r4 => r1 && r2 && r3 && r4)

while in the kyo Scala, we’d still just have:

    r1 <- userRepo.delete(userId)
    r2 <- changeRepo.deletePendingUserChanges(userId)
    r3 <- userRepo.save(newUser)
    r4 <- userRepo.someFn(userId)
yield r1 && r2 && r3 && r4

The effect is seamlessly combined with the other effects in the for comp.

if we didn’t want to propagate the same value, we’d instead recover or use a similar combinator (which we actually did in the transform function with the inner fetchUser function).

The Future of Effects Link to heading

I’d wager most people who are convinced of the benefits of typing in general see the value in tracking effects. While a lot of langauges take the approach of adding effect tracking to the language directly, this is quite limiting.

Not only do we have effects now that can be represented via AE/MTL and rarely are by reified effects 3, but there are future effects that may end up being very important to track safely.

If we take a look at the story of concurrency, we saw a lot of languages in the last half century that did not put concurrent computations at the forefront of language design, which ended up being a problem. It seemed to make sense at the time, most consumer grade computers were single core processors, but eventually multicore processors became the norm in most electronics.

A decent amount of work was required to add concise, safe and capable concurrency to these languages if they couldn’t express monads or AEs.

It’s quite possible that the same story will play out for something like quantum computing. We already see languages with quantum computing at the forefront of language design (Q# from Microsoft for example), but languages like Haskell and Scala already have expressive enough type systems that quantum computations can be tracked as a monad or AE (QIO lib in Haskell).

If we see wide consumer usage of QPUs, it’s likely languages that lack the expressive power to track effects generally will have trouble handling quantum computations, much like languages that lacked concurrency effect tracking fell into “callback hell”.

Further Reading Link to heading

If you want more code comparisons showcasing the different ways to track effects mentioned above, I have a page for that.


  1. if a/b are pure ↩︎

  2. unless checked exceptions are used, but this is generally seen as bad practice in Java because of how poor the ergonomics of exceptions are ↩︎

  3. effects that are rarely tracked by reified effects: Logging, caching/memoization, dependency management (alternative to DI frameworks), resource management (alternative to try/catch/finally or language constructs like with in Python), etc. Check out kyo’s core effects for some more examples if you’re interested. ↩︎ ↩︎

  4. often referred to as mtl style or just mtl, short for Monad Transformer Library ↩︎

  5. see Unison, Eff, or Effekt for examples of languages built from the start with algebraic effects in mind. ↩︎

  6. see kyo (scala) or polysemy (haskell) for AE libs. ↩︎