{{ message }}

Instantly share code, notes, and snippets.

Forked from jdegoes/Applied-FP-with-Scala.md
Created Dec 3, 2016

# 1. Mastering Functions

A function is a mapping from one set, called a domain, to another set, called the codomain. A function associates every element in the domain with exactly one element in the codomain. In Scala, both domain and codomain are types.

```val square : Int => Int = x => x * x

square(2) // 4```

## Higher-Order Functions

A higher-order function is a function that accepts or returns a function.

```trait List[A] {
def filter(f: A => Boolean): List[A]
}```

Example: `List[A].filter` is a higher-order function that accepts the function `A => Boolean` and returns the value `List[A]`.

## Combinators

Function combinators are higher-order functions that accept and return functions.

```type Conf[A] = ConfigReader => A

def string(name: String): Conf[String] = _.readString(name)

def both(left: Conf[A], right: Conf[B]): Conf[(A, B)] = c => (left(c), right(c))```

Example: `both` is a combinator that takes two functions and returns a function.

## Polymorphic Functions

A polymorphic function is one that is universally quantified over one or more type parameters. Scala has no support for polymorphic functions, but they can be emulated via polymorphic methods on traits. A trait modeling a polymorphic function usually has a single method called `apply`, so it can be applied with ordinary function application syntax.

```case object identity {
def apply[A](value: A): A = value
}
identity(3)   // 3
identity("3") // "3"```

Example: This emulates a polymorphic function called `id`, which accepts one type parameter `A`, and a value of type `A`, and returns that same value.

# 2. Mastering Types

## Type Theory 101

A �type is a compile-time description of a set of values. `Int` is the set of all integers between -2147483648 and 2147483647. Values have types, which is to say, they may be a member of the set of values they represent.

`2 : Int`

Example: `2` is a member of the set of all `Int`. Equivalently, `2` has type `Int`.

## Algebraic Data Types

An algebraic data type is a type formed by composing product and sum types.

### Product Type

Product types are defined by a Cartesian cross product on 2 or more types.

`type Point2D = (Int, Int)`

Example: A two-dimensional point is a product of a number and a number; each value has both an x-coordinate and a y-coordinate.

#### Case Classes

In Scala, case classes are the idiomatic representation of product types.

`case class Person(name: String, age: Int)`

Example: A person has both a string (`name`) and an integer (`age`).

### Sum Types

Sum types are defined by a disjoint union on 2 or more types.

`type RequestResult = Either[Error, HttpResponse]`

Example: An request result is a sum of `Error` and `HttpResponse`; each value is either an error or an HTTP response.

#### Sealed Traits

In Scala, sealed traits are the idiomatic representation of sum types (pre-Dotty).

```sealed trait AddressType
case object Home     extends AddressType

Example: An `AddressType` is either a `Home` or a `Business`, but not both.

## Subtyping

Type `A` is a subtype of `B` if \$A \subseteq B\$. In Scala, \$A\$ must extend \$B\$. The compiler allows subtypes to be used wherever a supertype is required.

```sealed trait Shape {
def width: Int
def height: Int
}
case class Rectangle(corner�: Point2D, width: Int, height: Int) extends Shape```

Example: A `Rectangle` is a subtype of `Shape`, because every `Rectangle` is a shape (but not every `Shape` is a `Rectangle`).

## Supertyping

Type `A` is a supertype of `B` if \$B \subseteq A\$. In Scala, \$B\$ must extend \$A\$. The compiler allows supertypes to be used wherever a subtype is provided.

In the previous example, `Shape` is a supertype of `Rectangle`, and a variable of type `Shape` may be assigned to a value of type `Rectangle`.

## Universals

A universally quantified type defines a category (or kind) of types that are all parameterized by some arbitrary type. In Scala, type constructors (such as traits) and methods may be universally quantified, although methods do not have a type (they are a component of a type).

## Type Constructors

A type constructor is a universally quantified type, which can be used to construct types.

``````sealed trait List[A]
case class Nil[A]() extends List[A]
case class Cons[A](head: A, tail: List[A]) extends List[A]
``````

Example: `List` is type constructor, which defines a category of `List`-like types, including `List[Boolean]` (the type of lists of booleans). `List` is said to be universally quantified over its type variable `A`.

## Higher-Kinded Types

### Type-Level Functions

Type constructors can be thought of as type-level functions, which accept types and return types. This interpretation is useful when reasoning about higher-kinded types.

Example: `List` is a type-level function that accepts one type `A` (the type of its elements), and returns another type `List[A]`. If you pass `Boolean` to `List`, you get back `List[Boolean]`, the type of lists of boolean values.

### Kinds

Kinds can be thought of as "the type of types".

• `*` — The kind of types (the set of all types).
• `* => *` — The kind of type-level functions that accept 1 type (the set of all type-level functions that accept 1 type). The type constructor `List` has kind `* => *`, represented as `_[_]` in Scala.
• `[*, *] => *` — The kind of type-level functions that accept 2 types (the set of all type-level functions that accept 2 types). The type constructor `Either` has kind `[*, *] => *`, represented as `_[_, _]` in Scala.

Note: Compare with the types of functions: `A => B`, `A => B => C`, `A => B => C => D`.

### Higher-Order Kinds

Just like functions can be "higher-order", type constructors can be higher-order, too. Scala uses underscores to encode higher-order type constructors. The declaration `trait CollectionModule[Collection[_]]` specifies that `CollectionModule`'s type constructor requires a type constructor of kind `* -> *` (such as `List`).

• `(* => *) => *` — The kind of type constructors that accept a type constructor of kind `* => *`. For example, `trait Functor[F[_]] { ... }` and `trait Monad[F[_]] { ... }`.

Note: All higher-order kinds that return a type (`*`) are valid kinds.

## Existentials

An existentially quantified type defines a type that depends on some definite but unknowable type. Existential types are useful for hiding type information that is not globally relevant.

```trait ListMap[A] {
type B
val list : List[B]
val mapf : B => A

def run : List[A] = list.map(mapf)
}```

Example: The type `ListMap[A]#B` is some definite type, but there is no way to know what that type is — it could be anything.

### Skolemization

Every existential type can be encoded as a universal type. This process is called skolemization.

```case class ListMap[B, A](list: List[B], mapf: B => A)

trait ListMapInspector[A, Z] {
def apply[B](value: ListMap[B, A]): Z
}

case class AnyListMap[A] {
def apply[Z](value: ListMapInspector[A, Z]): Z
}```

Example: Instead of using `ListMap` directly, we use `AnyListMap`, which allows us to inspect a `ListMap` but only if we can handle any type parameter for `B`.

## Type Lambdas

Functions may be partially applied with the underscore operator; e.g. `zip(a, _)`. A type lambda is a way to partially apply a higher-kinded type, which yields another type constructor with fewer type parameters.

Type lambdas are to type constructors as lambdas are to functions; the former are type/value expressions, while the latter are declarations.

`({type λ[α] = Either[String, α]})#λ`

Example: This is the `Either` type, partially applied with a `String` as the first type parameter.

Note: In many (but not all) cases, you can use type aliases instead of type lambdas (e.g. `type EitherString[A] = Either[String, A]`).

### Kind Projector

Kind Projector is a common compiler plugin for Scala that provides easier syntax to create type lambdas. For example, the type lambda `({type λ[α] = Either[String, α]})#λ` can be represented with the syntax `Either[String, ?]`. Other syntax can create more complex type lambdas.

https://github.com/non/kind-projector

# 3. Mastering Type Classes

A type class is a bundle of types and operations defined on them. Most type classes have laws that implementations are required to satisfy.

```trait ShowRead[A] {
def show(v: A): String
def read(v: String): Either[String, A]
}
def apply[A](implicit v: ShowRead[A]): ShowRead[A] = v
}```

Example: The `ShowRead[A]` type class defines a way of "showing" a type `A` by rendering it to a string, and reading it by parsing it from a string (or producing an error message).

• Right Identity

`read(show(v)) == Right(v)`
• Left Partial Identity

`read(v).map(show(_)).fold(_ => true, _ == v)`

## Instances

A type class instance, or simply instance, is an implementation of a type class for a given set of types. Such instances are usually made implicit so the compiler can thread them through functions that require them.

```implicit val ShowReadString: ShowRead[String] = new ShowRead[String] {
def show(v: String): String = v
def read(v: String): Either[String, String] = Right(v)
}

## Syntax

Convenient syntax, sometimes called extension methods, can be added to types to make it easier to use type classes.

```implicit class ShowOps[A: ShowRead](self: A) {
def show: String = ShowRead[A].show(self)
}
implicit class ReadOps(self: String) {
}

# 4. Mastering Functional Patterns

## Option, Either, Validation

These types are commonly used to describe optionality and partiality.

```sealed trait Maybe[A]
final case class Just [A](value: A) extends Maybe[A]
final case class Empty[A]()         extends Maybe[A]

sealed trait \/[A, B]
final case class -\/ [A, B](value: A) extends \/[A, B]
final case class  \/-[B, B](value: B) extends \/[A, B]

type Either[A, B] = A \/ B

sealed trait Validation[A, B]
final case class Failure[A, B](value: A) extends Validation[A, B]
final case class Success[A, B](value: B) extends Validation[A, B]```

## Semigroup, Monoid

Semigroups allows combining two things of the same type into another thing of the same type. For example, addition forms a semigroup over integers. Monoids add the additional property of having an "zero" element, which you can append to a value without changing the value.

```trait Semigroup[A] {
def append(a1: A, a2: A): A
}
trait Monoid[A] extends Semigroup[A] {
def zero: A
}```
• Associativity

`append(a1, append(a2, a3)) == append(append(a1, a2), a3)`
• Identity

`append(a, zero) == a`

## Functors

A functor `F[_]` is a type constructor of kind `* -> *`. In the most general case, an `F[A]` represents a description of a computation that may halt, run forever, or produce 0 or more `A`'s.

```trait Functor[F[_]] {
def map[A, B](fa: F[A])(ab: A => B): F[B]
}```

Note: Technically, this is a covariant endofunctor, and there are many other types of functors, including invariant and contravariant.

• Identity

`map(fa)(identity) == fa`
• Composition

`map(map(fa)(ab))(bc) == map(fa)(ab.andThen(bc))`

Example: `List` is a functor, and `List[Int]` is a trivial description of a computation producing some number of `Int`'s.

### Natural Transformations

A polymorphic function that maps from one functor `F[_]` to another functor `G[_]` is called a natural transformation, and is typically denoted using `F ~> G`. These functions are extremely important in higher-order functional programming.

```trait NaturalTransformation[-F[_], +G[_]] {
def apply[A](fa: F[A]): G[A]
}
type ~> [-F[_], +G[_]] = NaturalTransformation[F, G]```

Note: If you have `F ~> G`, and `G ~> H`, you can compose them to get `F ~> H`. In addition, for any `F`, there is an identity `F ~> F`.

### Functor Composition

Two functors can be composed together in a variety of ways to yield another functor.

#### Natural

The natural composition of two functors occurs when one is nested inside another.

`case class Composite[F[_], G[_], A](run: F[G[A]])`

#### Product

The product of two functors is a functor.

`case class Product[F[_], G[_], A](run: (F[A], G[A]))`

#### Coproduct

The sum (or coproduct) of two functors is a functor.

`case class Coproduct[F[_], G[_], A](run: Either[F[A], G[A]])`

### Lifting

Often, for some value `X`, `F[X]` is referred to as the "lifted" version of `X`, because it is the same value, but placed "inside" of some functor `F`. For example, you can lift the function `x => x * x` inside `List` by writing `List(x => x * x)`.

### Apply

Some functors implement `Apply`, which provides a way of applying a lifted function `F[A => B]` to some lifted value `F[A]` to yield `F[B]`.

```trait Apply[F[_]] extends Functor[F] {
def ap[A, B](fa: F[A])(fab: F[A => B]): F[B]
}```
• Associative Composition

```ap(ap(fa)(fab))(fbc) ==
ap(fa)(ap(fab)(map(fbc)(_.compose(_).curry))```

### Applicative

Some functors that implement `Apply` also implement `Applicative`, which provides the ability to lift any value into the functor.

```trait Applicative[F[_]] extends Apply[F] {
def point[A](a: A): F[A]
}```
• Identity

`ap(fa)(point(_)) == fa`
• Homomorphism

`ap(point(a))(point(ab)) == point(ab(a))`
• Interchange

`ap(point(a))(fab) == ap(fab)(point(_.apply(a)))`
• Derived Map

`map(fa)(ab) == ap(fa)(point(ab))`

### Bind

Some functors that implement `Apply` also implement `Bind`, which adds the ability to extend a computation `F[A]` with a second computation that depends on the result of `A` (`A => F[B]`), and collapse the result into a single computation `F[B]`.

```trait Bind[F[_]] extends Apply[F] {
def bind[A, B](fa: F[A])(afb: A => F[B]): F[B]
}```
• Associative Bind

`bind(bind(fa)(afb))(bfc) == bind(fa)((a) => bind(afb(a))(bfc))`
• Derived Ap

`ap(fa)(fab) == bind(fab)(map(fa)(_))`

Some functors that implement `Applicative` and `Bind` are `Monad`s.

`trait Monad[F[_]] extends Applicative[F] with Bind[F]`
• Right Identity

`bind(fa)(point(_)) == fa`
• Left Identity

`bind(point(a))(afb) == afb(a)`

### Other Types of Functors

• Invariant

```trait InvariantFunctor[F[_]] {
def xmap[A, B](ma: F[A], f: A => B, g: B => A): F[B]
}```
• Contravariant

```trait Contravariant[F[_]] extends InvariantFunctor[F] {
def contramap[A, B](r: F[A])(f: B => A): F[B]
}```
• Bifunctor

```trait Bifunctor[F[_, _]] {
def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]
}```

## Functional Collections

Structures `F[_]` that are `Foldable` are "containers", whose elements can be inspected.

### Foldable

```trait Foldable[F[_]] {
def foldMap[A,B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B
def foldRight[A, B](fa: F[A], z: => B)(f: (A, => B) => B): B
}```
• Consistent Left Fold

`foldMap(fa)(Vector(_)) == foldLeft(fa, Vector.empty[A])(_ :+ _)`
• Consistent Right Fold

`foldMap(fa)(Vector(_)) == foldRight(fa, Vector.empty[A])(_ +: _)`

### Traversable

Containers `F[_]` that define `Traverse` can be traversed in a way that rebuilds the original structure. The typical usage is sequencing, which is a way of type-flipping while preserving structure, transforming `F[G[A]]` into `G[F[A]]` for some `F[_]` which has a `Traverse`.

```trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
final def sequence[G[_]:Applicative,A](fga: F[G[A]]): G[F[A]] = ...
}```

Notes: Laws include identity, sequential fusion, purity, naturality, and parallel fusion.

# 5. Mastering Data

## Data & Codata

Data is a finite store of information, and may be non-recursive or recursive. Recursive data is sometimes called inductive data.

Codata is a description of a process for producing information, and may be non-corecursive or corecursive. Corecursive data is sometimes called coinductive data.

Finite data structures can be modeled with data or codata. Infinite data structures are modeled with codata.

## Church Encoding

The lambda calculus, the basis of functional programming, is sufficient to represent all possible data structures in an encoding known as Church encoding. Church encoding can sometimes be used to speed up operations, and other times to give you a better understanding of the fundamental properties of some data structure. Church encoding must be faked in Scala because Scala does not have true polymorphic functions (only polymorphic methods).

### Natural Numbers

```trait Natural { self =>
def fold[Z](zero: => Z, succ: Z => Z): Z

def succ: Natural = new Natural {
def fold[Z](zero: => Z, succ: Z => Z): Z = succ(self.fold(zero, succ))
}
def + (that: Natural): Natural = new Natural {
def fold[Z](zero: => Z, succ: Z => Z): Z = that.fold[Natural](self, _.succ).fold[Z](zero, succ)
}
def * (that: Natural): Natural = new Natural {
def fold[Z](zero: => Z, succ: Z => Z): Z =
that.fold[Natural](Natural.zero, _ + self).fold[Z](zero, succ)
}
def isZero: Boolean = fold[Boolean](true, _ => false)
def toInt: Int = fold[Int](0, _ + 1)
override def toString = toInt.toString
}
object Natural {
val zero = new Natural { def fold[Z](zero: => Z, succ: Z => Z): Z = zero }
def of(v: Int): Natural = if (v == 0) zero else of(v - 1).succ
}```

## Optics

Optics provide highly-composable, purely-functional machinery for focusing in on a part of a substructure `A` inside a superstructure `S` and performing local transformations to yield a new substructure `B` inside a new superstructure `T`. Different types of optics compose (for example, two lenses can be composed to yield another lens, but a lens and a prism yield an optional).

### Lens

Lenses provide a way to focus on a single term inside a product.

```abstract class PLens[S, T, A, B] extends Serializable { self =>
def get(s: S): A
def set(b: B): S => T
def modifyF[F[_]: Functor](f: A => F[B])(s: S): F[T]
def modify(f: A => B): S => T
}
type Lens[S, A] = PLens[S, S, A, A]```

### Prisms

Prisms provide a way to focus on a single term inside a sum.

```abstract class PPrism[S, T, A, B] extends Serializable { self =>
def getOrModify(s: S): T \/ A
def reverseGet(b: B): T
def getOption(s: S): Option[A]
}
type Prism[S, A] = PPrism[S, S, A, A]```

### Traversal

Traversals provide a way to focus on zero or more elements.

```abstract class PTraversal[S, T, A, B] extends Serializable { self =>
def modifyF[F[_]: Applicative](f: A => F[B])(s: S): F[T]
}
type Traversal[S, A] = PTraversal[S, S, A, A]```

### Fold

```abstract class Fold[S, A] extends Serializable { self =>
def foldMap[M: Monoid](f: A => M)(s: S): M
}```

### Getter

```abstract class Getter[S, A] extends Serializable { self =>
def get(s: S): A
}```

### Setter

```abstract class PSetter[S, T, A, B] extends Serializable { self =>
def modify(f: A => B): S => T
def set(b: B): S => T
}
type Setter[S, A] = PSetter[S, S, A, A]```

### Iso

Isos provide an isomorphism between an `A` in `S` and a `B` in `T`.

```abstract class PIso[S, T, A, B] extends Serializable { self =>
def get(s: S): A
def reverseGet(b: B): T
def reverse: PIso[B, A, T, S]
}
type Iso[S, A] = PIso[S, S, A, A]```

### Optional

```abstract class POptional[S, T, A, B] extends Serializable { self =>
def getOrModify(s: S): T \/ A
def set(b: B): S => T
def getOption(s: S): Option[A]
def modifyF[F[_]: Applicative](f: A => F[B])(s: S): F[T]
def modify(f: A => B): S => T
}
type Optional[S, A] = POptional[S, S, A, A]```

## Recursion Schemes

Recursion schemes are the ways that recursive and corecursive structures may be traversed, for purposes of altering them or inspecting them. For example, you can "fold" over a list to yield a new value. Using fixed-point data types, you can leverage generic recursion schemes that can work on any type of recursive or corecursive data structure.

### Fixed-Point Types

Fixed-point types factor out the recursion from recursive data structures. They operate on functors `F[_]` and extend them with recursion.

• Fix — Inductive or coinductive recursive structures. The simplest fixed-point type.

`final case class Fix[F[_]](unFix: F[Fix[F]])`
• Mu — Inductive (finite) recursive structures. For example, a JSON data structure.

```type Algebra[F[_], A] = F[A] => A

final case class Mu[F[_]](unMu: Algebra[F, ?] ~> Id)```
• Nu — Coinductive (possibly infinite) recursive structures. For example, a stream of values.

```sealed abstract class Nu[F[_]] {
type A
val a: A
val unNu: A => F[A]
}```
• Cofree[F[_], A] — A tree-like recursive structure whose nodes are annotated by values of type `A`.

`final case class Cofree[F[_], A](head: A, tail: F[Cofree[F, A]])`
• Free[F[_], A] — A tree-like recursive structure whose leaves may be values of type `A`.

```sealed trait Free[F[_], A]
final case class Pure[F[_], A](value: A) extends Free[F, A]
final case class Wrap[F[_], A)(unwrap: F[Free[F, A]]) extends Free[F, A]```

### Type Classes

Recursive and corecursive type classes allow you to abstract over the fixed-point type used to encode recursion or corecursion.

• Recursive`Mu` and `Nu` are recursive.

```trait Recursive[T[_[_]]] {
def project[F[_]: Functor](t: T[F]): F[T[F]]
}```
• Corecursive`Mu` and `Nu` are corecursive.

```trait Corecursive[T[_[_]]] {
def embed[F[_]: Functor](t: F[T[F]]): T[F]
}```

### Algebras

Algebras are single-step folds from a structure `F[_]`, while coalgebras are single-step unfolds to a structure `F[_]`. Both folds and unfolds may utilize some monadic effect `M[_]`, which may be the `Identity` monad.

• Algebra

```type Algebra[F[_], A] = F[A] => A
type AlgebraM[M[_], F[_], A] = F[A] => M[A]```
• Generalized Algebra

```type GAlgebra[W[_], F[_], A] = F[W[A]] => A
type GAlgebraM[W[_], M[_], F[_], A] = F[W[A]] => M[A]```
• Elgot Algebra

```type ElgotAlgebra[W[_], F[_], A] = W[F[A]] => A
type ElgotAlgebraM[W[_], M[_], F[_], A] = W[F[A]] => M[A]```
• Coalgebra

```type Coalgebra[F[_], A] = A => F[A]
type CoalgebraM[M[_], F[_], A] = A => M[F[A]]```
• Generalized Coalgebra

```type GCoalgebra[N[_], F[_], A] = A => F[N[A]]
type GCoalgebraM[N[_], M[_], F[_], A] = A => M[F[N[A]]]```
• Elgot Coalgebra

```type ElgotCoalgebraM[E[_], M[_], F[_], A] = A => M[E[F[A]]]
type ElgotCoalgebra[E[_], F[_], A] = A => E[F[A]]```

### Folds

Folds tear down a `Recursive` structure. These are some common schemes.

• Catamorphism

� def cata[F[_]: Functor, A](t: T[F])(f: Algebra[F, A]): A

``````* **Prepromorphism**

```scala
def prepro[F[_]: Functor, A](t: T[F])
(e: F ~> F, f: Algebra[F, A])(implicit T: Corecursive[T]): A
```
* **Paramorphism**

```scala
def para[F[_]: Functor, A](t: T[F])(f: GAlgebra[(T[F], ?), F, A]): A
``````
• Zygomorphism

`def zygo[F[_]: Functor, A, B](t: T[F])(f: Algebra[F, B], g: GAlgebra[(B, ?), F, A]): A`
• Histomorphism

`def histo[F[_]: Functor, A](t: T[F])(f: GAlgebra[Cofree[F, ?], F, A]): A`

### Unfolds

Unfolds build up a `Corecursive` structure. These are some common schemes.

• Anamorphism

`def ana[F[_]: Functor, A](a: A)(f: Coalgebra[F, A]): T[F]`
• Postpromorphism

```def postpro[F[_]: Functor, A](a: A)
(e: F ~> F, g: Coalgebra[F, A])(implicit T: Recursive[T]): T[F]```
• Apomorphism

`def apo[F[_]: Functor, A](a: A)(f: GCoalgebra[T[F] \/ ?, F, A]): T[F]`
• Futumorphism

`def futu[F[_]: Functor, A](a: A)(f: GCoalgebra[Free[F, ?], F, A]): T[F]`

### Refolds

Refolds tear down and build up a structure.

• Hylomorphism

`def hylo[F[_]: Functor, A, B](a: A)(f: Algebra[F, B], g: Coalgebra[F, A])): B`
• Dynamorphism

`def dyna[F[_]: Functor, A, B](a: A)(φ: F[Cofree[F, B]] => B, ψ: Coalgebra[F, A]): B`
• Codynamorphism

`def codyna[F[_]: Functor, A, B](a: A)(φ: Algebra[F, B], ψ: GCoalgebra[Free[F, ?], F, A]): B`
• Chronomorphism

```def chrono[F[_]: Functor, A, B](a: A)
(g: F[Cofree[F, B]] => B, f: A => F[Free[F, A]]): B```
• Elgot Algebra

`def elgot[F[_]: Functor, A, B](a: A)(φ: Algebra[F, B], ψ: CoalgebraM[B \/ ?, F, A]): B`
• coElgot Algebra

`def coelgot[F[_]: Functor, A, B](a: A)(φ: ElgotAlgebra[(A, ?), F, B], ψ: Coalgebra[F, A]): B`

### Transforms

Transforms are available on any type which acts as a functor transformer.

• Trans Catamorphism

`def transCataT[F[_]: Functor](t: T[F])(f: T[F] => T[F]): T[F]`
• Trans Anamorphism

`def transAnaT[F[_]: Functor](t: T[F])(f: T[F] => T[F]): T[F]`
• Trans Apomorphism

`def transApoT[F[_]: Functor](t: T[F])(f: T[F] => T[F] \/ T[F]): T[F]`
• Top-Down Catamorphism

`def topDownCata[F[_]: Functor, A](t: T[F], a: A)(f: (A, T[F]) => (A, T[F])): T[F]`

# 6. Mastering Effects

## IO

An `IO` abstraction converts effectful computations into pure values. This lets you write purely functional programs that are useful. The values have to be eventually executed, but only in the `main` function of the application.

```case class IO[A](unsafePerformIO: () => A) {
def map[B](ab: A => B): IO[B] =
IO(() => ab(unsafePerformIO()))
def flatMap[B](afb: A => IO[B]): IO[B] =
IO(() => afb(unsafePerformIO()).unsafePerformIO())
def tryIO(ta: Throwable => A): IO[A] =
IO(() => IO.tryIO(unsafePerformIO()).unsafePerformIO() match {
case Left(t) => ta(t)
case Right(a) => a
})
}
object IO {
def point[A](a: => A): IO[A] = IO(() => a)

def tryIO[A](a: => A): IO[Either[Throwable, A]] =
IO(() => try { Right(a) } catch { case t : Throwable => Left(t) })
}```

## State

A `State` monad allows retrieving and updating some arbitrary state `S`. Conceptually, the monad is a function from the old state, to both the new state and a value produced by the function.

```case class State[S, A](runState: S => (S, A)) {
def evalState(s: S): A = runState(s)._2
def execState(s: S): S = runState(s)._1
def map[B](ab: A => B): State[S, B] =
State(s => runState(s) match {
case (s, a) => (s, ab(a))
})
def flatMap[B](afb: A => State[S, B]): State[S, B] =
State(s => runState(s) match {
case (s, a) => afb(a).runState(s)
})
}
object State {
def point[S, A](a: A): State[S, A] = State(s => (s, a))
def get[S]: State[S, S] = State(s => (s, s))
def put[S](s: S): State[S, Unit] = State(_ => (s, ()))
def modify[S](ss: S => S): State[S, Unit] =
for { s <- get[S]; _ <- put(ss(s)) } yield ()
}```

A `Reader` monad allows reading from some environment `S`.

```case class Reader[S, A](runReader: S => A) {
def map[B](ab: A => B): Reader[S, B] = Reader(s => ab(runReader(s)))
def flatMap[B](afb: A => Reader[S, B]): Reader[S, B] =
}
def point[S, A](a: => A): Reader[S, A] = Reader(_ => a)
}```

## Combining Effects

In general, monadic effects do not combine. However, using type classes to abstract over effects enables composition of the requirements for an effect.

### Classes

```trait MonadIO[F[_]] {
def captureEffect[A](a: A): F[A]

def tryIO[A](fa: F[A]): F[Either[Throwable, A]]
}
def local[A](f: S => S)(fa: F[A]): F[A]
}
def init: F[S]
def get: F[S]
def put(s: S): F[Unit]
}

### Transformers

Monad transformers are abstractions that provide an effect (such as getting and setting state) that is layered on top of another, more powerful effect.

```trait MonadTrans[F[_[_], _]] {
def liftM[G[_] : Monad, A](a: G[A]): F[G, A]

/** The [[scalaz.Monad]] implied by this transformer. */
implicit def apply[G[_] : Monad]: Monad[F[G, ?]]
}```
• Identity

`liftM(G.point(a)) == Monad[F[G, ?]].point(a)`
• Composition

```liftM(Monad[G].bind(ga)(f)) ==
Monad[F[G, ?]].bind(liftM(ga))(a => liftM(f(a)))```

#### Common Transformers

• `StateT[F[_], S, A]` — Adds stateful operations atop `F[_]`.
• `StreamT[F[_], A]` — Adds non-determinism atop `F[_]`.
• `ReaderT[F[_], R, A]` — Adds reading "config" atop `F[_]`.
• `WriterT[F[_], W, A]` — Adds adds "logging" of monoidal `W` atop `F[_]`.
• `EitherT[F[_], E, A]` — Adds "errors" atop `F[_]`.
• `OptionT[F[_], A]` — Adds optionality atop `F[_]`.

# 7. Mastering Functional Architecture

Functional programs are comprised from smaller pieces. Small effects compose together to form larger effects. Small pieces of state compose together to form larger state. Small functions compose together to form "larger" functions.

Code that does not interact with external systems is easy to decompose. Code that interacts with external systems — so-called effects — can be decomposed in a way that depends on the application's overall architecture for effects.

## Onion Architecture

The onion architecture for FP involves layering semantic domains of the application. On the inside, the application speaks at the level of the domain model; at the outside, the application speaks the language of external effects.

Interpreters translate from an inner layer to an outer layer.

The onion architecture can be implemented with monad classes and transformers, or with free monads and similar structures of reified computation.

### Reified Computation

The purest and most powerful technique in representing effects involves reifying the structure and semantics of effectful computation. Standard abstractions such as the free monad and free applicative are useful.

A free monad provides a way to record and playback a sequential tree of operations described by some `F[_]`. Free monads provide a powerful way to describe all manner of effects using ordinary data structures that can be introspected, reflected, played back, and altered at runtime.

```sealed trait Free[F[_], A] { self =>
final def map[B](ab: A => B): Free[F, B] = Free.flatMap(self, ab andThen (Free.point[F, B](_)))
final def flatMap[B](afb: A => Free[F, B]): Free[F, B] = Free.flatMap(self, afb)

final def interpret[G[_]: Monad](fg: F ~> G): G[A] = self match {
case Free.Point(a0) => a0().point[G]
case Free.Effect(fa) => fg(fa)
case fm : Free.FlatMap[F, A] =>
val ga0 = fm.fa.interpret[G](fg)
ga0.flatMap(a0 => fm.afb(a0).interpret[G](fg))
}
}
object Free {
def point[F[_], A](a: => A): Free[F, A] = Point[F, A](() => a)
def liftF[F[_], A](fa: F[A]): Free[F, A] = Effect[F, A](fa)
private final case class Point[F[_], A](a0: () => A) extends Free[F, A]
private final case class Effect[F[_], A](fa: F[A]) extends Free[F, A]
private sealed trait FlatMap[F[_], B] extends Free[F, B] {
type A; def fa: Free[F, A]; def afb: A => Free[F, B]
}
private def flatMap[F[_], A0, B](fa0: Free[F, A0], afb0: A0 => Free[F, B]): Free[F, B] = new FlatMap[F, B] {
type A = A0; def fa = fa0; def afb = afb0
}
}```
##### Free Monad Example
```sealed trait ConsoleF[A]
final case class WriteLine(line: String) extends ConsoleF[Unit]
final case object ReadLine extends ConsoleF[String]

def writeLine(line: String): Free[ConsoleF, Unit] = WriteLine[ConsoleF, String](line)
def readLine: Free[ConsoleF, String] = Free.liftF[ConsoleF, String](ReadLine)

def example: Free[ConsoleF, Unit] = for {
_    <- writeLine("What is your name?")
_    <- writeLine("Hello, " + name + "!")
} yield ()```

### Deferring Effects

Pervasive use of type classes allows polymorphism in the implementation for an effect and supports painless large-scale refactoring. This pattern is associated with monad transformers (MTL) but it can be applied to free computations as well.

```trait Logging[F[_]] {
def log(v: String): F[Unit]
}
object Logging {
def apply[F[_]](implicit f: Logging[F]): Logging[F] = f
implicit def LoggingFree[F[_]: Logging]: Logging[Free[F, ?]] =
new Logging[Free[F, ?]] {
def log(v: String): Free[F, Unit] = Free.liftF(Logging[F].log(v))
}
}
}

def myFunctionThatLogs[F[_]: Logging: Monad] = ...```

#### Free Applicative

A free applicative provides a way to record and playback a parallel tree of operations described by some `F[_]`. It is not as expressive as a free monad, but it can be introspected all the way to the leaves, without runtime interpretation.

```sealed trait FreeAp[F[_], A] { self =>
final def map[B](ab: A => B): FreeAp[F, B] = FreeAp.map(self, ab)
final def ap[B](fab: FreeAp[F, A => B]): FreeAp[F, B] = FreeAp.ap(self, fab)

final def interpret[G[_]: Applicative](fg: F ~> G): G[A] = self match {
case FreeAp.Point(a0) => a0().point[G]
case FreeAp.Effect(fa) => fg(fa)
case fm : FreeAp.Map[F, A] => fm.fa.interpret[G](fg).map(fm.ab)
case fap : FreeAp.Ap[F, A] =>
val ga0 = fap.fa.interpret[G](fg)
ga0 <*> fap.fab.interpret[G](fg)
}
}
object FreeAp {
def point[F[_], A](a: => A): FreeAp[F, A] = Point[F, A](() => a)
def liftF[F[_], A](fa: F[A]): FreeAp[F, A] = Effect[F, A](fa)
private final case class Point[F[_], A](a0: () => A) extends FreeAp[F, A]
private final case class Effect[F[_], A](fa: F[A]) extends FreeAp[F, A]
private sealed trait Map[F[_], B] extends FreeAp[F, B] {
type A; def fa: FreeAp[F, A]; def ab: A => B
}
private sealed trait Ap[F[_], B] extends FreeAp[F, B] {
type A; def fa: FreeAp[F, A]; def fab: FreeAp[F, A => B]
}
private def ap[F[_], A0, B](fa0: FreeAp[F, A0], fa0b: FreeAp[F, A0 => B]): FreeAp[F, B] = new Ap[F, B] {
type A = A0; def fa = fa0; def fab = fa0b
}
private def map[F[_], A0, B](fa0: FreeAp[F, A0], a0b: A0 => B): FreeAp[F, B] = new Map[F, B] {
type A = A0; def fa = fa0; def ab = a0b
}
}```

#### Interpreters

Interpreters for reified computations often have the structure `F ~> T[G, ?]`, where `T` describes the computational context (sequential or parallel, for example), `F` describes the source operations, and `G` describes the target operations.

`type Interpreter[T[_[_], _], F[_], G[_]] = F ~> T[G, ?]`
• Horizontal Composition

Interpreters compose horizontally. You can compose `Interpreter[T, F, G]` and `Interpreter[T, G, H]` into `Interpreter[T, F, H]`. Stated differently, if you can interpret `F` to `G` in some context `T`, and `G` to `H` (in the same context), then you can interpret `F` to `H`.

• Vertical Composition

Interpreters compose vertically. You can compose `Interpreter[T, F, G]` and `Interpreter[T, F, H]` into `Interpreter[T, F, Product[G, H, ?]]`.

• Monoidal Composition

Interpreters compose monoidally as per the operations supported by `T[_[_], _]`. For example, if `T` supports a notion of failure, then two `T[F, A]` operations can be appended together, such that the first computation is used if it succeeds, otherwise the second. Racing is another example of monoidal composition possible with parallel computations.

#### Computation Contexts

Computation contexts `T[_[_], _]` are higher-order abstractions that reify computation. `Free` is a sequential context for computation, and a higher-order monad. `FreeAp` is a parallel context for computation, and a higher-order applicative.

#### Applications

Reified computation allows for dynamic introspection and transformation of a program's structure, including weaving effects (by composing interpreters), optimizing program structure (for parallel computational contexts), and even purely-functional mocking.

# Notices

Various code snippets and laws derive from Scalaz, Monocle, and Matryoshka. All rights are reserved via their respective copyright holders.

to join this conversation on GitHub. Already have an account? Sign in to comment