tomduhourq · September 13, 2016 17:01 · Sep 12, 2016
diff --git a/Advanced-FP-with-Scala.md b/Advanced-FP-with-Scala.md
@@ -0,0 +1,1190 @@
+# Advanced Functional Programming with Scala - Notes
+
+*Copyright &copy; 2017 Fantasyland Institute of Learning. All rights reserved.*
+
+# 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*.
+
+```scala
+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.
+
+```scala
+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. 
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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).
+
+```scala
+sealed trait AddressType
+case object Home     extends AddressType
+case object Business 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.
+
+```scala
+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.
+
+```scala
+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*.
+
+```scala
+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.
+
+```scala
+({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.
+
+```scala
+trait ShowRead[A] {
+  def show(v: A): String
+  def read(v: String): Either[String, A]
+}
+object ShowRead {
+  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**
+
+   ```scala
+   read(show(v)) == Right(v)
+   ```
+ * **Left Partial Identity**
+
+   ```scala
+   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.
+
+```scala
+implicit val ShowReadString: ShowRead[String] = new ShowRead[String] {
+  def show(v: String): String = v
+  def read(v: String): Either[String, String] = Right(v)
+}
+
+ShowRead[String].show("foo") // foo
+```
+
+## Syntax
+
+Convenient syntax, sometimes called *extension methods*, can be added to types to make it easier to use type classes.
+
+```scala
+implicit class ShowOps[A: ShowRead](self: A) {
+  def show: String = ShowRead[A].show(self)
+}
+implicit class ReadOps(self: String) {
+  def read[A: ShowRead]: Either[String, A] = ShowRead[A].read(self)
+}
+
+true.show.read[Boolean] // Right(true)
+```
+
+# 4. Mastering Functional Patterns
+
+## Option, Either, Validation
+
+These types are commonly used to describe optionality and partiality.
+
+```scala
+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.
+
+```scala
+trait Semigroup[A] {
+  def append(a1: A, a2: A): A
+}
+trait Monoid[A] extends Semigroup[A] {
+  def zero: A
+}
+```
+
+ * **Associativity**
+
+   ```scala
+   append(a1, append(a2, a3)) == append(append(a1, a2), a3)
+   ```
+ * **Identity** 
+
+   ```scala
+   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.
+
+```scala
+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**
+
+   ```scala
+   map(fa)(identity) == fa
+   ```
+ * **Composition**
+
+   ```scala
+   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.
+
+```scala
+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.
+
+```scala
+case class Composite[F[_], G[_], A](run: F[G[A]])
+```
+
+#### Product
+
+The product of two functors is a functor.
+
+```scala
+case class Product[F[_], G[_], A](run: (F[A], G[A]))
+```
+
+#### Coproduct
+
+The sum (or coproduct) of two functors is a functor.
+
+```scala
+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]`.
+
+```scala
+trait Apply[F[_]] extends Functor[F] {
+  def ap[A, B](fa: F[A])(fab: F[A => B]): F[B]
+}
+```
+
+ * **Associative Composition**
+
+    ```scala
+    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.
+
+```scala
+trait Applicative[F[_]] extends Apply[F] {
+  def point[A](a: A): F[A]
+}
+```
+
+ * **Identity**
+
+   ```scala
+   ap(fa)(point(_)) == fa
+   ```
+ * **Homomorphism**
+
+   ```scala
+   ap(point(a))(point(ab)) == point(ab(a))
+   ```
+
+ * **Interchange**
+
+   ```scala
+   ap(point(a))(fab) == ap(fab)(point(_.apply(a)))
+   ```
+
+ * **Derived Map**
+
+   ```scala
+   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]`.
+
+```scala
+trait Bind[F[_]] extends Apply[F] {
+  def bind[A, B](fa: F[A])(afb: A => F[B]): F[B]
+}
+```
+
+* **Associative Bind**
+
+  ```scala
+  bind(bind(fa)(afb))(bfc) == bind(fa)((a) => bind(afb(a))(bfc))
+  ```
+* **Derived Ap**
+
+  ```scala
+  ap(fa)(fab) == bind(fab)(map(fa)(_))
+  ```
+
+### Monad
+
+Some functors that implement `Applicative` and `Bind` are `Monad`s.
+
+```scala
+trait Monad[F[_]] extends Applicative[F] with Bind[F]
+```
+
+* **Right Identity**
+
+  ```scala
+  bind(fa)(point(_)) == fa
+  ```
+* **Left Identity**
+
+  ```scala
+  bind(point(a))(afb) == afb(a)
+  ```
+
+### Other Types of Functors
+
+ * **Invariant**
+
+   ```scala
+   trait InvariantFunctor[F[_]] {
+     def xmap[A, B](ma: F[A], f: A => B, g: B => A): F[B]
+   }
+   ```
+
+ * **Contravariant**
+
+   ```scala
+   trait Contravariant[F[_]] extends InvariantFunctor[F] {
+     def contramap[A, B](r: F[A])(f: B => A): F[B]
+   }
+   ```
+
+ * **Bifunctor**
+
+   ```scala
+   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
+
+```scala
+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**
+
+   ```scala
+   foldMap(fa)(Vector(_)) == foldLeft(fa, Vector.empty[A])(_ :+ _)
+   ```
+ * **Consistent Right Fold**
+
+   ```scala
+   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`.
+
+```scala
+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
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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.
+
+```scala
+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
+
+```scala
+abstract class Fold[S, A] extends Serializable { self =>
+  def foldMap[M: Monoid](f: A => M)(s: S): M
+}
+```
+
+### Getter
+
+```scala
+abstract class Getter[S, A] extends Serializable { self =>
+  def get(s: S): A
+}
+```
+
+### Setter
+
+```scala
+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`.
+
+```scala
+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
+
+```scala
+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.
+
+   ```scala
+   final case class Fix[F[_]](unFix: F[Fix[F]])
+   ```
+ * **Mu** — Inductive (finite) recursive structures. For example, a JSON data structure.
+
+   ```scala
+   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.
+
+ 	```scala
+ 	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`.
+
+   ```scala
+   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`.
+
+   ```scala
+   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.
+
+   ```scala
+   trait Recursive[T[_[_]]] {
+	  def project[F[_]: Functor](t: T[F]): F[T[F]]
+	}
+   ```
+ * **Corecursive** — `Mu` and `Nu` are corecursive.
+
+    ```scala
+    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**
+
+	```scala
+	type Algebra[F[_], A] = F[A] => A
+	type AlgebraM[M[_], F[_], A] = F[A] => M[A]
+	```
+ * **Generalized Algebra**
+
+	```scala
+	type GAlgebra[W[_], F[_], A] = F[W[A]] => A
+	type GAlgebraM[W[_], M[_], F[_], A] = F[W[A]] => M[A]
+	```
+ * **Elgot Algebra**
+
+	```scala
+	type ElgotAlgebra[W[_], F[_], A] = W[F[A]] => A
+	type ElgotAlgebraM[W[_], M[_], F[_], A] = W[F[A]] => M[A]
+	```
+ * **Coalgebra**
+
+
+	```scala
+	type Coalgebra[F[_], A] = A => F[A]
+	type CoalgebraM[M[_], F[_], A] = A => M[F[A]]
+	```
+ * **Generalized Coalgebra**
+
+
+	```scala
+	type GCoalgebra[N[_], F[_], A] = A => F[N[A]]
+	type GCoalgebraM[N[_], M[_], F[_], A] = A => M[F[N[A]]]
+	```
+ * **Elgot Coalgebra**
+
+
+	```scala
+	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**
+
+   ```scala
+   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**
+
+   ```scala
+   def zygo[F[_]: Functor, A, B](t: T[F])(f: Algebra[F, B], g: GAlgebra[(B, ?), F, A]): A
+   ```   
+* **Histomorphism**
+
+   ```scala
+   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**
+
+   ```scala
+   def ana[F[_]: Functor, A](a: A)(f: Coalgebra[F, A]): T[F]
+   ```
+* **Postpromorphism**
+
+   ```scala
+   def postpro[F[_]: Functor, A](a: A)
+     (e: F ~> F, g: Coalgebra[F, A])(implicit T: Recursive[T]): T[F]
+   ```
+* **Apomorphism**
+
+   ```scala
+   def apo[F[_]: Functor, A](a: A)(f: GCoalgebra[T[F] \/ ?, F, A]): T[F]
+   ```
+* **Futumorphism**
+
+   ```scala
+   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**
+
+   ```scala
+   def hylo[F[_]: Functor, A, B](a: A)(f: Algebra[F, B], g: Coalgebra[F, A])): B
+   ```   
+* **Dynamorphism**
+
+   ```scala
+   def dyna[F[_]: Functor, A, B](a: A)(φ: F[Cofree[F, B]] => B, ψ: Coalgebra[F, A]): B
+   ```   
+* **Codynamorphism**
+
+   ```scala
+   def codyna[F[_]: Functor, A, B](a: A)(φ: Algebra[F, B], ψ: GCoalgebra[Free[F, ?], F, A]): B
+   ```   
+* **Chronomorphism**
+
+   ```scala
+   def chrono[F[_]: Functor, A, B](a: A)
+     (g: F[Cofree[F, B]] => B, f: A => F[Free[F, A]]): B
+   ```   
+* **Elgot Algebra**
+
+   ```scala
+   def elgot[F[_]: Functor, A, B](a: A)(φ: Algebra[F, B], ψ: CoalgebraM[B \/ ?, F, A]): B
+   ```   
+* **coElgot Algebra**
+
+   ```scala
+   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**
+
+   ```scala
+   def transCataT[F[_]: Functor](t: T[F])(f: T[F] => T[F]): T[F]
+   ```
+ * **Trans Anamorphism**
+
+   ```scala
+   def transAnaT[F[_]: Functor](t: T[F])(f: T[F] => T[F]): T[F]
+   ```
+ * **Trans Apomorphism**
+
+   ```scala
+   def transApoT[F[_]: Functor](t: T[F])(f: T[F] => T[F] \/ T[F]): T[F]
+   ```
+ * **Top-Down Catamorphism**
+
+    ```scala
+    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.
+
+```scala
+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.
+
+```scala
+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 ()
+}
+```
+
+## Reader
+
+A `Reader` monad allows reading from some environment `S`.
+
+```scala
+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] =
+    Reader(s => afb(runReader(s)).runReader(s))
+}
+object Reader {
+  def point[S, A](a: => A): Reader[S, A] = Reader(_ => a)
+  def read[S]: Reader[S, S] = Reader(s => s)
+}
+```
+
+## 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
+
+```scala
+trait MonadIO[F[_]] {
+  def captureEffect[A](a: A): F[A]
+
+  def tryIO[A](fa: F[A]): F[Either[Throwable, A]]
+}
+trait MonadReader[F[_], S] {
+  def ask: F[S]
+  def local[A](f: S => S)(fa: F[A]): F[A]
+}
+trait MonadState[F[_], S] extends Monad[F] {
+  def init: F[S]
+  def get: F[S]
+  def put(s: S): F[Unit]
+}
+
+def myFunction[M[_]: MonadIO: MonadReader[?, S]] = ...
+```
+
+### 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.
+
+```scala
+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**
+
+   ```scala
+   liftM(G.point(a)) == Monad[F[G, ?]].point(a)
+   ```
+ * **Composition**
+
+   ```scala
+   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.
+
+#### Free Monad
+
+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.
+
+```scala
+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
+
+```scala
+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?")
+  name <- readLine
+  _    <- 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.
+
+```scala
+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.
+
+```scala
+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. 
+
+```scala
+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.