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.