IO: to be a Monad or not to be, that's the question!

Hello folks,
I promised you in How to live in a pure world I would have written a full article showing an example of how to deal with IO functionally and here it is!

I will use Kotlin and its functional companion library: Arrow.

A brief history of Arrow

Arrow was born as a merge of two functional libraries in the Kotlin universe: FunKtionale and Kategory. The contributors of the two libraries decided to join forces and so Arrow was born.

Like other libraries in other programming languages (like ScalaZ and Cats in Scala), Arrow tried to provide the same concepts of typed functional programming that were born in the Haskell universe: so they started out defining some core data types (Option, Try, Either, Validated, etc.) and a bunch of typeclasses like Functor, Semigroup, Monoid, Monad, and the likes (much more to be true).

The current version of Arrow is 0.11.0-SNAPSHOT. Arrow 0.11.0 should be released by September 2020, and the first major release should come out by the end of the year, even if it will not be marked as 1.0 but as 1.4, following the Kotlin compiler version (because of Arrow Meta).

What the team is working on to target the first stable release is to simplify and stabilize the api.

For example, they have already deprecated and they are going to remove the Try<A> data type, because it favors an eager evaluation of code that can have side effects, in favor of Either<E, A>. If you think about it you could say that:

typealias Try<A> = Either<Throwable, A> 

and the non-eager evaluation is granted by the fact that, aside for right/left value constructors, the function Either.catch() you use to wrap throwing blocks accepts only a suspended block (more on this later).

The same kind of simplification occurred also for Option<A>. There were some questions in the Kotlin community towards the actual need for such a data type, given the Kotlin language features nullable types. So Arrow maintainers have decided to ditch the Option data type in favor of nullable types or, once again, Eithers, providing also easy means to go from nullable types to Eithers. Example:

val a: A? = null 
val b: Either<Unit, A> = Either.fromNullable(a)
// and if you like you can define  
typealias Option<A> = Either<Unit, A> 

Monads

Before addressing the title question about whether or not IO should be modeled as a Monad, let's talk a bit about monads.

What is a Monad?

Last time I haven't spent much time on the subject because I wanted to focus more on the reason why IO operations were intrinsically impure

So, without further ado, here is maybe the most concise definition you could find about what a Monad is:

A monad is a monoid in the category of endofunctors.

The problem is this definition requires you to know what is a monoid, a category, and an endofunctor.

I'll try to provide you a short definition of all three.

Monoid

A monoid is a semigroup with a unit element, that respects the monoid laws. A semigroup is a set A with an internal operation, usually called combine, that is associative.

interface Semigroup<A> {
    fun combine(a: A, b: A): A
}

interface Monoid<A>: Semigroup<A> {
    val empty: A
}

The monoids laws are

1. associativity (because it's a semigroup): for all a,b,c in A it must be true that combine(a,combine(b,c)) = combine(combine(a,b),c)
2. left identity: for all a in A combine(empty,a) = a
3. right identity: for all a in A combine(a,empty) = a

Category

This is a bit more abstract. A category C is a pair (O, M) where

• O is a collection of objects (we are not interested in better defining them)
• M is a collection of morphisms that connects an object A in O to an object B (m: A -> B)

For C to be a category it must obey to the category laws:

1. There must exist for every A in O an identity morphism 1_A: A -> A
2. There must exist an operation, called composition, indicated by . such that for every 2 morphisms in M, f: A -> B and g: B -> C, it exists a morphism g . f: A -> C. This operation must have 2 properties
   1. associativity: for every 3 morphism in M, f: A -> B, g: B -> C and h: C -> D then it must be true that (f . g) . h = f . (g . h)
   2. identity: for every f: A -> B then 1_A . f = f . 1_B

Why are categories relevant for programmers? Well, because you can say that a programming language is a category where

• O is the collection of its types
• M are the functions
• The composition of morphism is the composition of functions.

Functor

What is a functor? It's a map between categories that preserves the category structure. To be more precise, given 2 categories C and D, F is a functor if

• for every object X in C, it maps an F(X) in D
• for every morphism f: A -> B in C it maps the morphism F(f) = F(A) -> F(B) in D
• for every X in C it maps the identity morphism in C into the identity morphism in D, i.e. F(1_xC) = 1_F(X)D
• for every two morphism in C, f and g, F(f . g) = F(f) . F(g)

An endofunctor is just a functor from a category C into C itself.

Given the previous parallelism drawn between a category and a programming language, you might be wondering: what is an endofunctor in a programming language?
Well, if you think about it, it should be something that maps its types (the objects) but also its functions (the morphisms) between the basic types (from the original category) into functions between the mapped types (in the new category, the one where all the objects have the form F<X>).

So an endofunctor F in Kc (the Kotlin types category) is a pair F = (F(X), lift) where

• F(X) is a type constructor (i.e. F(X) is a new type in Kc)

• lift is a function
  

      fun <A,B> lift(f:(A) -> B): F<A> -> F<B>
  

I guess all this might seem a bit abstract, so an example might help.

Ex.: Option<A> is a functor.

Why? Because it is a type constructor (from A to Option<A>) and it exist a lift function

    fun <A,B> lift(f:(A) -> B): Option<A> -> Option<B> = 
        { a: Option<A> -> a.map(f) }

Putting it all together

From all the definition above we can come back to a more operative definition of a monad: a monad is a type constructor with three functions

// pseudo code (to actually encode a generic monad one has to encode first the concept of higher kinded types)
interface Monad<A> {
    fun of(t: A): Monad<A> = // omitted
    fun <B> map(ma: Monad<A>, f: (A) -> B): Monad<B> = // omitted
    fun <B> flatMap(ma: Monad<A>, f: (A) -> Monad<B>): Monad<B> = // omitted
}

that obeys to the following laws

• left identity: flatMap(of(x), f) = f(x)
• right identity: flatMap(x, of) = x
• associativity: flatMap(flatMap(ma, f), g) = flatMap(mx) {x -> flatMap(f(x), g) }

Note: the actual encoding in Arrow of Monads is a bit different, the above pseudo-code was made just to give a general idea.

IO monad

IO is a monad and in Arrow is undergoing the same simplification process shown above for the core data types: more specifically it's going to be deprecated and removed from the library (this time not in favor of Either).

The reasons in this case are different.

The first one is that Kotlin has a language feature (suspended functions and coroutines) that can better express the intent of a data type like IO<A>, with native support in the language.

Secondly, if you ever try to write actual programs using IO, you will probably end up with something like IO<Either<E, A>>, that is not so ergonomic to work with.

Let's see it with an example (finally, am I right?)

data class FileName(val path: String)
data class Employee(
  val lastName: String, 
  val firstName: String, 
  val birthDate: LocalDate, 
  val emailAddress: EmailAddress
)
data class EmailAddress(val value: String)

sealed class ProgramError
data class ReadFileError(val path: String): ProgramError()
data class ParseError(val source: String): ProgramError()
data class MailSendingError(
  val emailMessage: EmailMessage
): ProgramError()

typealias Program = 
    (FileName) -> IO<Either<ProgramError, Unit>>
typealias LoadEmployees = 
    (FileName) -> IO<Either<ProgramError, List<Employee>>>
typealias EmployeeFilter = (Employee) -> Boolean
typealias SendBirthdayGreetings = 
    (Employee) -> IO<Either<ProgramError, Unit>>

fun createSendGreetingsFunction(
    loadEmployees: LoadEmployees,
    employeeBornToday: EmployeeFilter,
    sendBirthDayGreetingMail: SendBirthdayGreetings
): Program = { sourceFile: FileName ->
    EitherT(loadEmployees(sourceFile)).flatMap { employees ->
        employees
            .filter(employeeBornToday)
            .map { e -> EitherT(sendBirthDayGreetingMail(e)) }
            .sequence().map { Unit }
    }.value().fix()
}

This is a snippet of code from my take on the birthday greetings kata by Matteo Vaccari (full code here, tag io-either-version-arrow-0.10.5).

The code per se is pretty straightforward: it will load a list of employees from a csv file, filter the employees born today and then send them a birthday greeting email.

To execute the program description built using IOs one need to do something like the following at the edge of his/her world (the main function, your rest controller, etc.)

val program = sendGreetingsToAll(FileName("/fixtures/bigFile.csv"))
program.unsafeRunSync()

NOTE: one common mistake one can make is to continuously create and run IOs. That is not the way (or it is not supposed to be). You should build your entire description of what your program does and then only run it once at the end of your world (so to speak).

The following are the functions in the previous snippet of code that have a side effect and have been modeled with IO

typealias LoadEmployees = 
    (FileName) -> IO<Either<ProgramError, List<Employee>>>
typealias SendBirthdayGreetings = 
    (Employee) -> IO<Either<ProgramError, Unit>>
typealias Program = 
    (FileName) -> IO<Either<ProgramError, Unit>>

What is the issue with them?
Well, it's something related to their composition.
Given that their return type is an Either nested inside an IO, working with it becomes a little cumbersome because, even if they are both Monads (IO and Either), and monads should make it easier to sequence transformations, having two nested monads you should first map or flatMap on the external one, IO, and then on the internal one, Either.

One would have hoped to be able to write

val f: (A) -> IO<Either, B> = // omitted
val a: IO<Either<E, A>> = // whatever
val b: IO<Either<E, B>> = a.flatMap(f)

But it's not possible. You have to write something like this

val f: (A) -> IO<Either, B> = // omitted
val ioA: IO<Either<E, A>> = // whatever
val ioB: IO<Either<E, B>> = 
    ioA.flatMap { eitherA: Either<E, A> -> 
        eitherA.fold(
            { e: E -> IO.just(e.left()) }, 
            { theActualA: A -> f(theActualA) }  
        )

That's the reason why you have seen in my previous snippet that EitherT. What is it? It is a Monad Transformer and let you compose two nested monads in case the inner one is an Either; in lemon terms, it's a data type that wraps the IO<Either<E, A>> and let you regain the easiness of sequencing operations.

Let's see how that would apply in the last example

val f: (A) -> IO<Either, B> = // omitted
val ioA: IO<Either<E, A>> = // whatever
val ioB: IO<Either<E, B>> = 
    EitherT(ioA).flatMap { theActualA: A -> 
        EitherT(f(theActualA)) 
    }.value().fix()

Monad transformers solve a problem, i.e. the fact that two Monads cannot be generically composed to produce another monad; the question is: is it the right problem to solve?
We have introduced IO to re-gain purity and referential transparency but it also adds already one wrapper layer around our impure logic; if, when we are using IO in real life, we end up having an IO<Either<E, A>>, and to work with it we have to use an EitherT, adding another extra layer with both a cognitive and performance overhead, one might ask: is it worth it?

Suspended functions

The answer is: maybe no. In Arrow 0.11.0-SNAPSHOT the maintainers decided to ditch the IO monad in favour of suspended functions. What does it mean? Let's have a look at the sendBirthdayGreetings example revised

typealias LoadEmployees = 
    suspend (FileName) -> Either<ProgramError, List<Employee>>
typealias EmployeeFilter = (Employee) -> Boolean
typealias SendBirthdayGreetings = 
    suspend (Employee) -> Either<ProgramError, Unit>
typealias SendGreetings = 
    suspend (FileName) -> Either<ProgramError, Unit>

fun createSendGreetingsFunction(
    loadEmployees: LoadEmployees,
    employeeBornToday: EmployeeFilter,
    sendBirthDayGreetingMail: SendBirthdayGreetings
): SendGreetings = { sourceFile: FileName ->
    loadEmployees(sourceFile).flatMap { employees ->
        employees
            .filter(employeeBornToday)
            .map { e -> sendBirthDayGreetingMail(e) }
            .sequence().map { Unit }
    }
}

Can you spot the difference? That's right here it is

typealias LoadEmployees = 
    suspend (FileName) -> Either<ProgramError, List<Employee>>
typealias SendBirthdayGreetings = 
    suspend (Employee) -> Either<ProgramError, Unit>
typealias SendGreetings = 
    suspend (FileName) -> Either<ProgramError, Unit>

All the functions that returned an IO<Either<ProgramError, A>> in the previous version, now simply return an Either<ProgramError, A> but are marked as suspend, signaling they need a safe environment to be executed (arrow-fx-coroutines provides such an environment).

So the suspend functions take the place of functions returning IO because they are, for all intent and purposes, delayed and conveying the same concept as the IO monad: something impure is going on.

Here is how you could run the previous function at the end of your world (in my case in the acceptance test)

import arrow.fx.coroutines.Environment

Environment().unsafeRunSync {
    sendGreetingsToAll(FileName("/fixtures/bigFile.csv"))
}        

Easy, no?

Conclusion

IO: to be a Monad or not to be?

Arrow guys answer is: no, thank you. We have already a Kotlin construct that is more than enough to describe impure interactions with the external world: suspended functions.

What else? I don't know, I only hope to have given you a feel of how to use IO, monad, or not, in a real-life example.

---

References

• Arrow docs
• Bartosz Milewski category theory for programmers: videos, book
• Giulio Canti functional programming notes (only for those of you who speak Italian and are versed in Typescript)
• Scott Wlaschin visual explanation of the elevated world
• A nice little post explaining functors, applicatives, monoids and monads in pictures

Comments

[Raúl Raja Martínez]

Suspended functions can be a replacement for all monads because continuations are the mother of all monads.

We could define NonDet and Either exclusively in terms of suspension. We are gonna bring suspension and imperative FP to all data types not just IO as described in this excellent article by @eureka84 and eliminate as much nested style as possible to make FP truly ergonomic in Kotlin.

We have already built shift/reset and a polymorphic ContT over suspension exclusively and two primitives that allow for a la carte strategies per datatype wherein strict ones we can simply fold and suspended ones suspend and resume in any thread.

Continuation also let us flatten three layers of transformers so binding is interleaved.
you can bind in place io, either, io of either and either of io.
nobody is doing this and there is no need to lift to a particular context.

The ergonomics of continuations and the duality of imperative programming has been historically disregarded because most langs have been copying the indirect Haskell encoding. Nothing wrong with that but the JVM prioritizes an imperative stack and labelled loop over reified data structures that need to be folded and interpreted as in most IOs in the JVM except Arrow Fx Coroutines.

But what I would like to bring to your attention with this comment is that suspend is not a replacement for IO but all monads and foldable (see SequenceBuilder in the std lib) and can support interleaved transformer binding at all layers of the transformers, also effect handlers and really anything since it isn't restricted to monads. We have proven monoidal builders as well and there is more we are researching drastically how FP is seen from Kotlin and it's all thanks to the suspension and compiler CPS transformation

Thank you Angelo again for this excellent article, we don't talk enough about these things.
Jannis, Simon and I are currently working on this if anyone wants to get in touch and find out more and get involved. Cheers!

[Iven Marquardt]

You write that Kotlin can avoid monadic nesting in some/many cases using delimited continuations based on suspend functions. I am currently researching on this topic in the JS context, where we have generator functions. The problem is that such functions can only resume once at a specific position, but to flatten monadic computations in general we'd need multi-shot continuations. How do you solve that in Kotlin? Are Kotlin suspened functions multi-shot? Maybe you can provide some external resources?

[Iven Marquardt]

Think I answered my own q: The Kotlin compiler performs a CPS transformation under the hood, similar to Haskell's do block transformation to nested >>=.

[Raúl Raja Martínez]

yes and while multishot is not supported since they are single-shot delimited, you can still multi prompt and build multi-shot like continuations with it.

[Iven Marquardt]

But what I would like to bring to your attention with this comment is that suspend is not a replacement for IO but all monads and foldable (see SequenceBuilder in the std lib) and can support interleaved transformer binding at all layers of the transformers

This is very interesting to me. Can you provide further resources?

[Raúl Raja Martínez]

schoolofhaskell.com/school/to-infi...

blog.poisson.chat/posts/2019-10-26...

gallium.inria.fr/~scherer/research...

And check out the multiple impls of ContT. Here goes one in swift:
gist.github.com/sjoerdvisscher/a56...

This great discussion about them in Kotlin gist.github.com/elizarov/5bbbe5a3b...
( we got passed the multiprompt issue thanks to Jannis but have not had time to update the combo)

Hope this helps.

[Iven Marquardt]

Thanks for taking the time. Kotlin seems to be very interesting in the sense of a different approach to FP than Haskell.

[Iven Marquardt]

Suspended functions seem to be a replacement for the IO type, not the IO monad. A more idiomatic IO type for Kotlin so to speak. You probably can write a monad instance for suspended functions, but I am not that familiar with Kotlin so I may be wrong.

but are marked as suspend, signaling they need a safe environment to be executed (arrow-fx-coroutines provides such an environment).

This sound like Haskell's main function, which is always of type IO and interprets at runtime what the IO actions mean in the real world.

[Raúl Raja Martínez]

Compared to Haskell suspend functions would be like lang special syntax support for something like ContT. But suspension can be generalized to other monads. See the Kotlin std lib SequenceBuilder which is unrelated to IO and builds collections lazily. See also this comment for a more in-depth look into what we are doing dev.to/raulraja/comment/13a8h

[Angelo Sciarra]

Yeah, the intent is to become more idiomatic.
I don't know much about Haskell (just read a bit "Learn you a Haskell for Great Good" but never actually used it).

[Adam Warski]

Thanks for the post! I'm coming mostly from a Scala background, so it's good to get to know what's happening in Kotlin, especially that Java seems to be taking a similar route with Loom.

I've got a question though about the programming model. When working with IO, we're working with side-effect-free/pure functions, and get a number of benefits like referential transparency (we also get some non-benefits, but that's covered in your article). However, when we shift to working with suspended functions, don't we once again move back to working with side-effecting code?

That is, moving from IO to suspended functions would mean moving from FP to imperative/procedural programming. (And maybe that's fine - for performance and readability reasons.)

Another question is can you "lift" a suspended function to a value? While I see how suspended functions provide for much more readable code when it comes to sequential logic, I think for writing concurrent programs (even something as simple as running computations in parallel and combining their results) the lifted representation might be better.

[Angelo Sciarra]

Hi Adam,
thank you for reading it! Well the thing is that suspended functions are not like usual functions and need a context (a CoroutineContext) to be run in.
In that sense they are special and can be considered like descriptions of a side effect because, as for IO monad and monads in general, once you work with a supended function it "infects" all calling functions, meaning you either provide a coroutine context, same as unwrapping the IO by running it, or mark also the caller function as suspended (use map or flatMap).
In that sense I don't think it fosters an imperative style (from a phylosophical point of view you could also say that Monads enable an imperative style in the FP world).
To answer your second question I think a suspended identity function is an equivalent of pure/point/return/just whatever you want to call it.
About concurrent facilities I invite you to have a look at arrow-fx-coroutines, it provides all the functions you may already know (tupledN, parMapN, raceN, and others) ant it is designed with suspended functions.

Hope to have provided you an answer.

[Adam Warski]

Thanks! This definitely makes sense - so a suspended function is automatically lazily evaluated, which is really what IO is under the covers (a lazily evaluated function () => T or () => Future[T]).

And you are right that monads enable imperative style in FP - nothing wrong with that I suppose, depending of course on the definition of imperativeness and FP (as these unfortunately aren't that precise). But imperative understood as running a sequence of steps is something that's very natural and common in programming.

Here's what I found for raceN. As far as I see, it's taking suspend () -> A parameters to avoid eager evaluation of the computations that are being passed in. So in a way, these values are double-lazy (one because of the suspension, two because of the () ->)?

So I guess (thinking aloud here) you could say that the representation of a computation as a value is suspend () -> T (where T is the result of the computation).

One problem that I would see here is that the representation of a computation isn't uniform. Sometimes it's () => T, sometimes it's just T. If I would e.g. want to race a two processes, I would write something like val result1 = raceN(() -> a, () -> b).

But if I want to race this with yet another computation at some point in the future, it's not enough to write val result2 = raceN(() -> result, () -> c). I have to go back and change result1 to be a no-params function. Thinking about it, I think I just described lack of referential transparency of the Kotlin solution.

Not sure how much of a problem it is in practice. But for sure it's some departure from what IO and "pure FP" (again, depending how you define FP) gives you.

[Angelo Sciarra]

In your example about race keep in mind that saying it takes suspend () -> A is equivalent to taking as input IO[A] (as far as I understood).

For a better explanation read here, especially the sections Arrow Fx vs Tagless Final and Goodbye Functor, Applicative, and Monad.

[Adam Warski]

Thanks for the link! I think my reservations come from the fact that with IO you have the following signature: race(a: IO[A], b: IO[B]): IO[Either[A, B]]. While with suspensions, you have: race(a: suspend () -> A, b: suspend () -> B): Either[A, B].

Note that the return type doesn't return our "effect type", that would be () -> Either[A, B], but an eagerly evaluated value (Either[A, B]). And this matters for composition, meaning that if you want to compose that process later with others, you'll have to keep that in mind when defining it.

Hence it seems we're trading the uniformity of IO and some composition properties for the better readability and performance of suspensions. As always, tradeoffs :)

[Babis]

I have high expectations from Arrow.

Currently, I cannot consider it as a viable option for production applications, simply because library is not mature and is changing drastically with each version (0.7, 0.8, 0.9, 0.10, 0.11).
This is a good thing because innovation requires disruptive changes. The idea to use idiomatic Kotlin to represents monads is great and most importantly would make more appealing the use of the FP among imperative programmers.

At some point we need though a milestone version

[Raúl Raja Martínez]

This is coming up this year when the Kotlin IR backend is stable in the 1.4.x series. We almost feature complete for 0.11 and stable comes after that one.

[Eljay-Adobe]

One of the things I've grown to really like about F# is every function is a monad.

I've even implemented some monad magic in C++, but it isn't idiomatic C++ because functional programming is not idiomatic C++.

[pentacular]

The critical insight for I/O is that your output is only a side-effect if it can influence your input. :)

[Angelo Sciarra]

(see here)