This note is about functional effects including what is functional effect and how to compose different effects. It is based on the video: One Monad to Rule Them All.

## 1 Intro to Functional Effects

Functional programming takes many concepts and turns them into data. Functional programming are proficient in manipulating, transforming and refactoring values. Use functions to remove duplications across multiple expressions. Use varaibles to revome duplications in a single expression. Use combinators to remove/extracting duplications across chains or workflows of common operations. Use value equality for testing.

Types, methods, packages, input/output (side-effect statement), cases (of enumeration or terms of sum type), and fields (for example two field of a case class) are not first-class values. Jonh defines a functional effect as “an immutable data type equipped with a set of core operations that together provide a complete, type-safe model of a domain concern”. An interpreter interpretes the data structures and execute the corresponding actions.

There is an effect and an execution for each concern. For example:

Concern Effect Execution
Optionality Option[A] null or A
Disjunction Either[A, B] A or B
Nondeterminism List[A] Option[A]
Input/Output IO[A] throw or value

An example of a `Maybe` type can be defined in three steps:

### 1.1 Step 1: Define the data structure

 ``````1 2 3 4 5 6 7 `````` ``````sealed trait Maybe[+A] case class Present[A](value: A) extends Maybe[A] case object Absent extends Maybe[Nothing] case class Map[A, B](maybe: Maybe[A], mapper: A => B) extends Maybe[B] case class Chain[A, B](first: Maybe[A], callback: A => Maybe[B]) extends Maybe[B]``````

The data structure is used to describe the effects to be applied. The `Map[A, B]` represents a `mapper` that convert a value. The `Chain[A, B]` is used to chain effects together. An example chain of effects could be:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````val double: Int => Int = _ * 2 val eff1 = Chain[Int, Int]( Present(42), a => Map(Present(a), double) ) val eff2 = Chain[Int, Int]( Absent, a => Map(Present(a), double) )``````

### 1.2 Step 2: Interpreter

An interpreter will interpret a description and generate the result. An interpret has three parts: a `Maybe[B]` value of type `B`, a specified value of type `C` if it is `Absent`, and a `f: B => Z` function that process the result of the description structure.

 ``````1 2 3 4 5 6 7 8 `````` ``````def interpret[Z, A, B](ifAbsent: Z, f: B => Z)(maybe: Maybe[B]): Z = maybe match { case Present(b) => f(b) case Absent => ifAbsent case Map(old, f0: (A => B)) => interpret(ifAbsent, f compose f0)(old) case Chain(old, g: (A => Maybe[B])) => interpret(ifAbsent, (a: A) => interpret(ifAbsent, f)(g(a)))(old) }``````

The interpret can be used to execute the effect description such as `interpret(eff1)` and `interpret(eff2)`, the results are `168` and `-1`.

### 1.3 Step 3: `for` Expression

Nested data structrue in step1 is not easy to write and read, therefore add `map`, `flatMap` and factory methods:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````sealed trait Maybe[+A] { self => def map[B](f: A => B): Maybe[B] = Map(self, f) def flatMap[B](f: A => Maybe[B]): Maybe[B] = Chain(self, f) } object Maybe { def present[A](value: A): Maybe[A] = Present(value) def absent: Maybe[Nothing] = Absent }``````

Then the description can be written as the following:

 ``````1 2 3 4 5 6 7 `````` `````` val forEff1 = for { a <- present(42) } yield double(a) val forEff2 = for { a <- Absent } yield double(a)``````

### 1.4 Core Operations for Functional Effects

Every operation in a functional effect system has a corresponding functional type class.

Operation Signature Functional Type Class
pure/point A => F[A] Applicative
map (F[A], A => B) => F[B] Functor
flatMap (F[A], A => F[B]) => F[B] Monad
zip/ap [F[A], F[B]] => F[(A, B)] Apply

The `flatMap` composite two effects by using a effect result as the input to a callback. The `zip` operation combines two effects into a single value side by side. Three basic operations are `pure`, `map` and `zip` to support transformation and result combination. A more powerful functional effect system uses `flatMap` to support sequential operations that uses the first effect result as the input to the second. The Scala `for` expression enables a procedure syntax.

## 2 Tour of the Effect Zoo

A functional effect is an immutable data type, together with the operations it provides to address some business concerns. At the end of the day, every functional effect system need to be executed/interpreted to perform actions and generate results. The interpretation is `fold` on `Option`, `unsafeRun` on `Task`. An Interpretation runs on the state monda: taking the description and turning it into something useful.

### 2.1 Option

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 `````` ``````// Option data types sealed trait Option[+A] final case class Some[+A](value: A) extends Option[A] final case class None extend Option[Nothing] // core operations def some[A](a: A): Option[A] = Some(a) val none: Option[Nothing] = None def map[A, B](o: Option[A], f: A => B): Option[B] def flatMap[A, B](o: Option[A], f: A => Option[B]): Option[B] // Execution / Interpretation: z is the value for None value def fold[Z](z: Z)(f: A => Z)(o: Option[A]): Z``````

### 2.2 Either

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````// Either data types sealed trait Either[+E, +A] final case class Left[+E](value: E) extends Either[E, Nothing] case class Right[+A](value: A) extends Either[Nothing, A] // core operations def left[E](e: E): Either[E, Nothing] = Left(e) def left[E](a: A): Either[Nothing, A] = Right(a) def map = ... def flatMap = ... def fold[Z, E, A](left: E => Z, right: A => Z)(e: Either[E, A]): Z``````

### 2.3 Writer

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````// logging data type: it accumulates logs of type W into a Vector, it produces a value of type A // it cannot fail final case class Writer[+W, +A](run: (Vector[W], A)) // core operations def pure[A](a: A): Writer[Nothing, A] = Writer((Vector(), a)) def write[W](w: W): Writer[W, Unit] = Writer((Vector(w), ())) def map[W, A, B](o: Writer[W, A], f: A => B): Writer[W, B] def flatMap[W, A, B](o: Writer[W, A], f: A => Write[W, B]): Write[W, B] // execution def run[W, A](writer: Writer[W, A]): (Vector[W], A)``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````// State is a functional effect that models stateful computation. It is basically a function. final case class State[S, +A](run: S => (S, A)) // core operations def pure[S, A](a: A): State[S, A] = State[S, A](s => (s, a)) def get[S]: State[S, S] = State[S, S](s => (s, s)) def set[S](s: S): State[S, Unit] = Statep(S, Unit)(_ => (s, ())) def map = ??? def flatMap = ??? // execution def run[S, A](s: S, state: State[S, A]): (S, A)``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````// Reader is a context of a proram that can be pulled out anytime final case class Reader[-R, +A](run: R => A) // core operations def pure[A](a: A): Reader[Any, A] = Reader[Any, A](_ => a) def environment: Reader[R, R] = Reader[R, R](r => r) def map = ??? def flatMap = ??? // execution def privide[R, A](r: R, reader: Reader[R, A]): A``````

### 2.5 IO

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 `````` ``````// an asynchronous IO runs a function in the future final case class IO[+A](unsafeRun: (Try[A] => Unit) => Unit) // core operations def sync[A](v: => A): IO[A] = IO(_ => Success(v)) def aysnc[A](r: (Try[A] => Unit) => Unit): IO[A] = IO(r) def fail(t: Throwable): IO[Nothing] = IO(_ => Failure(t)) def map = ??? def flatMap = ??? // execution takes an io and a callback with either success or failure def unsafeRun[A](io: IO[A], k: Try[A] => Unit): Unit``````

The commone things for all these effects:

• immutable data structure
• composable operations: `pure`, `map`, and `flatMap`
• execution that translate value or handle errors

## 3 Vertical Effect Composition

The above functions are not useful because they are not composable. To combine `Option` with `Either`:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````final case class OptionEither[+E, +A](run: Either[E, Option[A]]) { def map = ??? def flatMap = ??? } object OptionEither { def pure[A](a, A): OptionEither[Nothing, A] = lift(Some(a)) def lift[A](option: Option[A]): OptionEither[Nothing, A] = OptionEither(Right(option)) }``````

To abstract over the type, use HKT that uses effect inside effect, so-called monad transformer. It can vertically compose effects.

 ``````1 2 3 4 5 6 7 8 9 `````` ``````final case class OptionT[F[_], +A](run: F[Option[A]]) { def map = ??? def flatMap = ??? } object OptionT { def pure[A, F](a: A)(implicit F: Applicatoin[F]): Option[F, A] = lift(Some(a)) def lift[A, F](option: Option[A])(implicit F: Applicative[F]): OptionT[F, A] = OptionT(F.pure(option)) }``````

The monad transformer can tranform all above functional effects except IO effect. Monad transformers allow local effect introduction and elmination.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````def myCode[F[_]: Monda]: F[Result] = { // introduce state effect locally def inner: StateT[F, MyState, Result] = ??? // eliminate state effect locally inner.run(MyState.Initial) } // if need multiple monad composition type GodMonad[+E, +W, S, -R, A] = OptionT[ EitherT[ WriterT[ StateT[ Reader[R, ?], S, ?] W, ?] E, ?] ?]``````

Monad transformer has the performance issue because multiple closures add a lot overhead. It is also order sensitive. N layers has N! possibilities. Tagless final can reduce the layers, however, it doesn’t all local effect introduction and elminiation.