Functional Effects

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
empty /zero	F[Nothing]	MonadPlus
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)

2.4 Reader

 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.

Table of Contents