One_concept_to_explain_them_all_and_in_the_theory_bind_them.scala

/*
  This piece of commented code aims to clarify some
  misconceptions between several advanced concepts
  in pure functional programming/category theory:
  free monads, finally tagless approach, algebraic
  effects.

  These concepts are actually very close. They rely
  on similar concepts and even represent the "same"
  object (up to isomorphism!) from the theoretical
  point of view.

  I do not address the theoretical aspects here.
  Instead, i present, the same example, the well-known
  factorial function, in each approach to highlight
  the connections between them.

  This presentation is made for people already used
  to program with monads and type-classes. No mathematical
  background is required, if you are comfortable with IO,
  Future and others, you'll be fine!
*/

/*
  Let's start by some definitions
*/

import scala.language.higherKinds

object CommonDefinitions {

  /* I want this presentation to be self-contained,
     so here is a basic definition of what a monad is.
  */
  trait Monad[F[_]] {
    def pure[A](a: A): F[A]
    def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]
    
  }

  /* To ease the presentation, some syntactic sugar is
     welcome. This implicit class will provide methods
     map and flatMap on values `F[A]` where `F`
     has an instance of `Monad` just above
  */
  implicit class SyntaxHelper[F[_],A](val self: F[A])(implicit F: Monad[F]) {
    def flatMap[B](f: A => F[B]): F[B] =
      F.flatMap(self)(f)

    def map[B](f: A => B): F[B] =
      F.flatMap(self)((a:A) => F.pure(f(a)))
  }

  /*
    Most presentation need some examples. This
    one will use the Writer effect. Put it simply,
    it is a monad that simulates `println`.

    In order to avoid confusion, the effect of
    printing a string to an output channel is
    called `log`
  */
  trait WriterTypeClass[F[_]] extends Monad[F] {
    /** Print this message somewhere.
      * The actual behavior depends on the nature of `F`.
      */
    def log(message: String): F[Unit]

    // Yes it is already in Monad, but it doesn't hurt to be explicit
    def pure[A](a: A): F[A]

    // Yes it is already in Monad, but it doesn't hurt to be explicit
    def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]
  }
}
import CommonDefinitions._

/*
   Now that the stage is set, we can begin.
   The first approach is the more direct one: the effect
   is encoded as a monad named `Writer`.
*/
object IFearAbstractionApproach {

  /** A object of `Writer[A]` is a value of type `A` and
      a collection of strings which collects the messages
      that are output by `log`
  */
  final case class Writer[A](value: A, logs: Vector[String])

  /** This presentation being consistent, `Writer` is indeed
      related to the subject and so has an instance of the
      type-class `WriterTypeClass`
  */
  implicit object Writer extends WriterTypeClass[Writer] {
    def pure[A](a: A): Writer[A] =
      Writer(a, Vector.empty)
    
    def log(message: String): Writer[Unit] =
      Writer((), Vector(message))
    
    def flatMap[A,B](wa: Writer[A])(f: A => Writer[B]): Writer[B] = {
      val wb: Writer[B] = f(wa.value)
      Writer(wb.value, wa.logs ++ wb.logs)
    }
  }

  /** Thus we can write the factorial function
      which logs each step.

      Note that logging here is an effect, but
      not a side-effect. Side effects are hidden
      effects that do not appear in the type
      signature. On the contrary, `fact` is a pure
      function that returns a value `Writer[Int]`.

      This not a side-effect but a visible-effect.
  */
  def fact(n: Int): Writer[Int] =
    if (n <= 0)
      for {
        _ <- Writer.log("last recursion!")
        r <- Writer.pure(1)
      } yield r
    else
      for {
        _ <- Writer.log(s"still $n recursion to do!")
        r <- fact(n-1)
      } yield n * r
    
  val test = fact(10)
  /* res0: IFearAbstractionApproach.Writer[Int] =
         Writer(3628800, Vector(still 10 recursion to do!,
                                ...
                                still 1 recursion to do!, last recursion!))
  */
}

import IFearAbstractionApproach._

/*
  Last example was just to some warm-ups to make you feel comfortable.
  It's about time to dive into the real subject!

  Let's start by the free monad seen as an algebraic data type.
  The goal here is not to present the free monad in all its in all its
  generality but to give an honest and simple presentation. So the
  definition below is not exactly the one you may see on other materials.
  But it is completely equivalent to the free monad (and freeer monad)
  as it is often introduced plus the `Log` effect so we have a complete,
  ready-to-use definition.
*/

object FreeMonad_AlgebraicDataTypesAllTheWayDown {

  /** This is the type of the Free Monad bundled with the `Log`
      effect.
  */
  sealed abstract class FreeWriter[A]
  final case class Pure[A](value: A) extends FreeWriter[A]
  final case class FlatMap[X,A](arg: FreeWriter[X], f: X => FreeWriter[A]) extends FreeWriter[A]
  final case class Log(message: String) extends FreeWriter[Unit]

  /** This presentation still being consistent, `FreeWriter` also has
      an instance of `WriterTypeClass`
  */
  implicit object FreeWriter extends WriterTypeClass[FreeWriter] {
    def pure[A](a: A): FreeWriter[A] =
      Pure(a)
 
    def log(message: String): FreeWriter[Unit] =
      Log(message)
 
    def flatMap[A,B](fa: FreeWriter[A])(f: A => FreeWriter[B]): FreeWriter[B] =
      FlatMap(fa, f)

    /** /!\ VERY IMPORTANT!

        This methods says that a `FreeWriter[A]` can be transformed into
        an `F[A]` for any type `F` which has an instance of `WriterTypeClass`,
        i.e. any type `F` that is a monad and has a `Log` effect.

        It means `FreeWriter` is not just a monad with `Log` effect, it is "the"
        most general one! We will see very soon what "the" means.
    */
    def interpret[F[_], A](fw: FreeWriter[A])(implicit F: WriterTypeClass[F]): F[A] =
      fw match {
        case Pure(a)       => F.pure(a)
        case Log(message)  => F.log(message)
        case fm: FlatMap[x,a] =>
          val wx: F[x] =
            interpret[F,x](fm.arg)

          def f(v: x): F[a] =
            interpret[F, a](fm.f(v))
          
          F.flatMap(wx)(f)
      }
  }

  /** Same `fact` function, but this time
      with `FreeWriter`
  */
  def fact(n: Int): FreeWriter[Int] =
    if (n <= 0)
      for {
        _ <- FreeWriter.log("last recursion!")
        r <- FreeWriter.pure(1)
      } yield r
    else
      for {
        _ <- FreeWriter.log(s"still $n recursion to do!")
        r <- fact(n-1)
      } yield n * r
    
  val freeTest = fact(10)
  /* res1: FreeMonad_AlgebraicDataTypesAllTheWayDown.FreeWriter[Int] =
      FlatMap(Log(still 10 recursion to do!),
              FreeMonad_AlgebraicDataTypesAllTheWayDown$$$Lambda$1553/534217155@3fb2d0a3
             )
  */

  // This is so simple to get back the `Writer` implementation!
  val interpretTest = FreeWriter.interpret[Writer, Int](freeTest)
  /* res2: IFearAbstractionApproach.Writer[Int] =
         Writer(3628800, Vector(still 10 recursion to do!,
                                ...
                                still 1 recursion to do!, last recursion!))
  */
}
import FreeMonad_AlgebraicDataTypesAllTheWayDown._

/*
  The Free Monad is cool! Actually the free monad WAS cool in 2015. What
  was cool in 2018 was ... FINALLY TAGLESS (imagine some fireworks and
  cheering crowd). But what FINALLY TAGLESS is all about?
*/
object FreeMonad_as_FINALY_a_newspeak_name_for_an_old_TAG_LESS_bankable {

  /* Finally tagless, at first look, is close to this.
     Note that `fact` here is parameterized by a generics
     `F[_]` for which we have an instance of `WriterTypeClass[F]`.

     It means fact is able to compute a value `F[Int]` of any type `F`
     providing that `F` is a monad and supports the `Log` effect.
     (Note that `F` may support many more effect!).

     Is it not familiar? Have a look at the `FreeWriter.interpret` function.
  */ 
  def fact_NOT_TAGLESS[F[_]](n: Int)(implicit F: WriterTypeClass[F]): F[Int] =
    if (n <= 0)
      for {
        _ <- F.log("last recursion!")
        r <- F.pure(1)
      } yield r
    else
      for {
        _ <- F.log(s"still $n recursion to do!")
        r <- fact_NOT_TAGLESS[F](n-1)
      } yield n * r

  /*
    We are not in Haskell but in Scala! In Haskell the type
    of fact would be (using Scala type syntax):

      fact: Int => (forall (F[_]: WriterTypeClass) => F[Int])

    The "forall" is very important. We can not write the return type
    that way in Scala:

      type FinallyTaglessWriter[A] = (forall (F[_]: WriterTypeClass) => F[A])

    But we can make it a trait! Note that the `interpret` method has
    exactly the desired type signature!
  */
  trait FreeMonadRebrandedAsFinallyTagless[A] {
    def interpret[F[_]](implicit F: WriterTypeClass[F]): F[A]
  }

  type FreeFT[A] = FreeMonadRebrandedAsFinallyTagless[A]

  /* Now we can give `fact its real type:

       fact: Int => FreeFT[Int]

    Look how `fact_REAL_TAGLESS` is just `fact_NOT_TAGLESS` with boilerplate that
    is still necessary because Scala, unlike Haskell, does not support RankNTypes.
  */
  def fact_REAL_TAGLESS(n: Int): FreeFT[Int] =
    new FreeMonadRebrandedAsFinallyTagless[Int] {

      def interpret[F[_]](implicit F: WriterTypeClass[F]): F[Int] = fact_NOT_TAGLESS[F](n)

    }
  

  /** I really like my presentations being consistent, so `FreeFT` also has
      a `WriterTypeClass` instance
  */
  implicit object FreeMonadRebrandedAsFinallyTagless extends WriterTypeClass[FreeFT] {
    def pure[A](a: A): FreeFT[A] =
      new FreeMonadRebrandedAsFinallyTagless[A] {
        def interpret[F[_]](implicit F: WriterTypeClass[F]): F[A] = F.pure(a)
      }

    
    def log(message: String): FreeFT[Unit] =
      new FreeMonadRebrandedAsFinallyTagless[Unit] {
        def interpret[F[_]](implicit F: WriterTypeClass[F]): F[Unit] = F.log(message)
      }
    
    def flatMap[A,B](fa: FreeFT[A])(f: A => FreeFT[B]): FreeFT[B] =
      new FreeMonadRebrandedAsFinallyTagless[B] {
        def interpret[F[_]](implicit F: WriterTypeClass[F]): F[B] = {
          val arg: F[A] = fa.interpret[F]
          def g(a: A): F[B] = f(a).interpret[F]

          F.flatMap(arg)(g)
        }
      }
  }
  
  /** One again, we can transform a `FreeFT[A]` into any type `F` which
      is at least a monad with supports the `Log` effect!

      This is exactly the same property that we noticed about `FreeWriter`.
      It means `FreeFT` is ALSO "the"most general monad with the `Log` effect!
      
      Wait?! Wasn't `FreeWriter` already "the" most general one? How could `FreeFT`
      be this one too? The answer is actually pretty simple: `FreeWriter` and `FreeFT`
      are equivalent. Note that they are not identical, they do not behave
      the same way, they have different performance properties, etc. But regarding
      only what they can compute, they are actually equivalent: we can convert values
      at will between these two types.
  */
  def interpret[F[_]: WriterTypeClass, A](fa: FreeMonadRebrandedAsFinallyTagless[A]): F[A] =
    fa.interpret[F]

  def freeAsTagless2ADT[A](fa: FreeFT[A]): FreeWriter[A] =
    fa.interpret[FreeWriter]

  def freeAsADT2Tagless[A](fa: FreeWriter[A]): FreeFT[A] =
    FreeWriter.interpret[FreeFT, A](fa)

  val test_NOT_TAGLESS = fact_NOT_TAGLESS[Writer](10)
  /* res4: IFearAbstractionApproach.Writer[Int] =
        Writer(3628800,Vector(still 10 recursion to do!,
                              ...
                              still 1 recursion to do!, last recursion!))
  */

  val test_REAL_TAGLESS = fact_REAL_TAGLESS(10).interpret[Writer]
  /* res5: IFearAbstractionApproach.Writer[Int] =
        Writer(3628800,Vector(still 10 recursion to do!,
                              ...
                              still 1 recursion to do!, last recursion!))
  */
}
import FreeMonad_as_FINALY_a_newspeak_name_for_an_old_TAG_LESS_bankable._

/* Finally Tagless WAS cool back in 2018! But we are in 2019 now. What is cool
   in 2019 is algebraic effects!

   In a nutshell, the goal of algebraic effect, is to have declarative effects,
   like what we have done so far but without an encoding like previous examples.
   One technique to implement them is with "resumable exceptions" which are
   exceptions but unlike the ones you may be used to, with these ones you can
   resume the computation that was interrupted.

   It is sounds familiar to you, this is perfectly normal. This behavior has
   many names but the most common one is continuations. I will not present what
   continuations are here. If you want to know more about the subject, please
   read [Olvier Danvy's excellent disseration](https://www.cs.uoregon.edu/research/summerschool/summer09/lectures/danvy-dissertation.pdf)
*/

object AlgebraicEffects {
  
  /** The effect we are interested in!
      Note that `WriterEffect` is not a monad! It is
      not even a functor. It just defines the `Log`
      effect and nothing else!
    */
  sealed trait WriterEffect[A]
  final case class Log(message: String) extends WriterEffect[Unit]

  /* A handler is something that can translate `WriterEffect[A]`
     into actual computations. Yes, this is once again the very
     same story but presented differently.

     Note again that `F` is still not required to be a monad.
   */
  trait Handler[F[_]] {
    def interpret[A](wa: WriterEffect[A]): F[A]
  }


  /* Fortunately we can derive an `Handler` from `WriterTypeClass` */
  object Handler {
    def fromWriterTypeClass[F[_]](implicit F: WriterTypeClass[F]): Handler[F] =
      new Handler[F] {
        def interpret[A](wa: WriterEffect[A]): F[A] =
          wa match {
            case Log(message) => F.log(message)
          }
      }
  }

  /* As i told you, algebraic effects can be implemented using "resumable exceptions"
     which are nothing more than restricted continuations (restricted because they often
     can be resumed at most once, while continuations can be resumed at will).

     To simulate "resumable exceptions" we will use continuations, the continuation monad
     in fact. An effect will interrupt the computation, so wee need a way to store the
     effect launched to be able to handle it, and also the continuation to be able to
     resume the computation.

     This leads to an `EffectStream`
  */
  sealed trait EffectStream[A]
  /** The computation is finished, `value` is the computed value */
  final case class End[A](value: A) extends EffectStream[A]
  /** The computation is not finished, but has been interrupted by an effect.
      The effect and the continuations are stored
  */
  final case class Effect[X,A](effect: WriterEffect[X], continuation: X => EffectStream[A]) extends EffectStream[A]

  /** Just the continuation monad whose return type is `EffectStream[R]` for any `R` */
  trait ContWriter[A] {
    def run[R](continuation: A => EffectStream[R]): EffectStream[R]
  }

  /** Do you remember how the `WriterTypeClass` is defined? It is so by extending the `Monad`
      type-class with a `log` method. This is exactly equivalent to having a monad `F` with
      a `Handler[F]`.

      Which means an `EffectStream[A]` can be interpreted/transformed into any type `F` which is
      a monad provided that there is a handler for the effects.
  */
  object EffectStream {
    def interpret[F[_],A](es: EffectStream[A], handler: Handler[F])(implicit F: Monad[F]): F[A] =
      es match {
        case End(a) =>
          F.pure(a)

        case eff: Effect[x,a] =>
          val fx: F[x] =
            handler.interpret(eff.effect)
          
          def g(v: x): F[a] = {
            val es2: EffectStream[A] = eff.continuation(v)
            interpret[F, A](es2, handler)
          }
          
          F.flatMap(fx)(g)
      }
  }

  /** Still consistent! `ContWriter` also has an instance of `WriterTypeClass`
  */
  implicit object ContWriter extends WriterTypeClass[ContWriter] {
    
    def pure[A](a:A): ContWriter[A] =
      new ContWriter[A] {
        def run[R](continuation: A => EffectStream[R]): EffectStream[R] =
          continuation(a)
      }
    
    def log(message: String): ContWriter[Unit] =
      new ContWriter[Unit] {
        def run[R](continuation: Unit => EffectStream[R]): EffectStream[R] =
          Effect(Log(message), continuation)
      }
    
    def flatMap[A,B](fa: ContWriter[A])(f: A => ContWriter[B]): ContWriter[B] =
      new ContWriter[B] {
        def run[R](continuation: B => EffectStream[R]): EffectStream[R] =
          fa.run { (a: A) =>
            f(a).run(continuation)
          }
      }

    
    /** Unsurprisingly, a `ContWriter[A]` can be transformed into any monad `F` with
        a `Log` effect handler. This is once again the same property that `FreeWriter`
        and `FreeFT` satisfy. `ContWriter[A]` is also "the" most general monad with
        a `Log` effect.

        It means `FreeWriter`, `FreeFT` and `ContWriter` are all equivalent. Of course
        they are not identical. They have different performance properties and one
        may be better suited than another in a specific setting. But regarding only
        what their abstract behavior, they are equivalent.
    */
    def interpret[F[_]: Monad,A](fa: ContWriter[A], handler: Handler[F]): F[A] = {
      val effectStream: EffectStream[A] = fa.run(End(_))
      EffectStream.interpret[F,A](effectStream, handler)
    }
  }


  /** `fact` using the `ContWriter` approach. */
  def fact(n: Int): ContWriter[Int] =
    if (n <= 0)
      for {
        _ <- ContWriter.log("last recursion!")
        r <- ContWriter.pure(1)
      } yield r
    else
      for {
        _ <- ContWriter.log(s"still $n recursion to do!")
        r <- fact(n-1)
      } yield n * r
    
  val factAsCont       = fact(10)

  // All equivalent ...
  val factAsFreeWriter = ContWriter.interpret[FreeWriter, Int](factAsCont, Handler.fromWriterTypeClass[FreeWriter])
  val factAsFreeFT     = ContWriter.interpret[FreeFT    , Int](factAsCont, Handler.fromWriterTypeClass[FreeFT    ])
  val factAsWriter     = ContWriter.interpret[Writer    , Int](factAsCont, Handler.fromWriterTypeClass[Writer    ])
}

import AlgebraicEffects._

/*
=====  Conclusion ==========

This is not obvious, at first sight, that `FreeWriter`, `FreeFT` and `ContWriter`
are actually equivalent. Every approach seem very different from the two others.
But they are all "the" free monad. They are all instances of the same abstract
concept: being "the" most general of their kind, up to equivalence.

This is why, as developers, we should not focus too much on what some definition
looks like but also which property they satisfy because two apparently very
different concepts may actually be completely equivalent.

Equivalence means we can switch, without loosing information, from one form
to another. This is very important in practice because it means we can switch
to the representation which is the best suited per task!

I hope you enjoyed this presentation. Feel free to contact me if you have remarks,
questions, etc.

Take care.
*/

IFearAbstractionApproach.test
FreeMonad_AlgebraicDataTypesAllTheWayDown.freeTest
FreeMonad_AlgebraicDataTypesAllTheWayDown.interpretTest
FreeMonad_as_FINALY_a_newspeak_name_for_an_old_TAG_LESS_bankable.test_NOT_TAGLESS
FreeMonad_as_FINALY_a_newspeak_name_for_an_old_TAG_LESS_bankable.test_REAL_TAGLESS
AlgebraicEffects.factAsCont
AlgebraicEffects.factAsFreeWriter
AlgebraicEffects.factAsFreeFT
AlgebraicEffects.factAsWriter