EugenioMoggi.scala

// Lambda World 2019 - A categorical view of computational effects - Emily Riehl
// https://www.youtube.com/watch?v=Ssx2_JKpB3U

object EugenioMoggi {

    // normal functions
    type Function[A, B] = A => B
    // they compose
    def composeFunctions[A, B, C]:
        (Function[A, B], Function[B, C]) => Function[A, C] =
            (fab, fbc) => a => fbc(fab(a))

    // functions with effect (aka Kleisli)
    type FunctionWithEffect[F[_], A, B] = A => F[B]
    // note that A => F[B] can be seen as
    // - a normal function whose return type happens to be F[B]
    // - an "effectful" function from A to B with an effect F
    // the difference is in how we want to compose them
    // - if the next function in the chain is F[B] => Whatever, then it is just normal function composition
    // - if the next function is B => F[C], then we want to compose FunctionWithEffects:
    def composeFunctionsWithEffects[F[_], A, B, C]:
        (FunctionWithEffect[F, A, B], FunctionWithEffect[F, B, C]) => FunctionWithEffect[F, A, C] =
            (fab, fbc) => a => bind(fbc)(fab(a))
    // so an effect is any type constructor F[_], provided that when you return F[B],
    // you actually want to compose in terms of B

    // having bind is equivalent to having composeFunctionsWithEffects above
    // one can be expressed in terms of the other, as is done here just for the sake of excercise
    def bind[F[_], A, B]: FunctionWithEffect[F, A, B] => FunctionWithEffect[F, F[A], B] =
        fab => fa => composeFunctionsWithEffects[F, Unit, A, B](Function.const(fa), fab)(())

    // the above implementations of bind and composeFunctionsWithEffects are of course mutually recursive and won't work
    // in real life there would be a special implementation of e.g. bind for each F[_], such as List, Option, IO
}