## Natural transformation

``````trait ~>[F[_], G[_]] {
def apply[A](f: F[A]): G[A]
}``````

``````trait Monad[M[_]] {
def pure[A](x: A): M[A]
def map[A, B](x: M[A])(f: A => B): M[B] = flatMap(x)(a => pure(f(a)))
def flatMap[A, B](x: M[A])(f: A => M[B]): M[B]
}``````

## ID

``````type ID[A] = A

override def pure[A](x: A): ID[A] = x
override def flatMap[A, B](x: ID[A])(f: A => ID[B]): ID[B] = f(x)
}``````

``````trait Free[F[_], A] {

import Free._

def map[B](f: A => B): Free[F, B] = flatMap { a => pure(f(a)) }

def flatMap[B](f: A => Free[F, B]): Free[F, B] = Bind(this, f)

def foldMap[G[_]: Monad](nt: F ~> G): G[A] = this match {
case Pure(a) =>
case Suspend(fa) =>
nt(fa)
case Bind(fa, f) =>
val ga = fa.foldMap(nt)
mg.flatMap(ga)(f(_).foldMap(nt))
}
}

case class Pure[F[_], A](a: A) extends Free[F, A]
case class Suspend[F[_], A](fa: F[A]) extends Free[F, A]
case class Bind[F[_], A, B](fa: Free[F, A], f: A => Free[F, B]) extends Free[F, B]

object Free {

def pure[F[_], A](a: A): Free[F, A] = Pure(a)

def liftM[F[_], A](fa: F[A]): Free[F, A] = Suspend(fa)
}``````

## Usage

``````trait Program[A]
case class ReadEnv(name: String) extends Program[String]
case class Write(output: String) extends Program[Unit]``````
``````val enProgram: Free[Program, Unit] =
for {
_    <- Free.liftM(Write("What's your name? "))
_    <- Free.liftM(Write(s"Hello, \${name}!\n"))
} yield ()

val esProgram: Free[Program, Unit] =
for {
_    <- Free.liftM(Write("¿Cómo te llamas? "))
_    <- Free.liftM(Write(s"¡Hola, \${name}!\n"))
} yield ()

val program: Free[Program, Unit] =
for {
_    <- if (lang.startsWith("es")) {
esProgram
} else {
enProgram
}
} yield ()``````
``````program.foldMap[ID] {
new ~>[Program, ID]{
def apply[A](x: Program[A]): ID[A] =
x match {
case Write(output) => print(output)
}
}
}``````

## Demo

This file is literate Scala, and can be run using Codedown:

``````\$ curl https://earldouglas.com/posts/effect-systems/free.md |
codedown scala > script.scala
\$ LANG=es scala -nc script.scala
¿Cómo te llamas? James
¡Hola, James!``````