Docs: more articles

gcanti · Jan 9, 2020 · 9e40af2 · 9e40af2
1 parent b42d385
commit 9e40af2
Show file tree

Hide file tree

Showing 12 changed files with 761 additions and 1 deletion.
diff --git a/docs/functional-design/combinators-part-I.md b/docs/functional-design/combinators-part-I.md
@@ -1,5 +1,5 @@
 ---
-title: Combinators
+title: Combinators Part I
 parent: Functional design
 nav_order: 1
 ---

diff --git a/docs/getting-started/Applicative.md b/docs/getting-started/Applicative.md
@@ -0,0 +1,177 @@
+---
+title: Applicative
+parent: Getting started
+nav_order: 7
+---
+
+# Getting started with fp-ts: Applicative
+
+In the [last](https://dev.to/gcanti/getting-started-with-fp-ts-functor-36ek) post we saw that we can compose an effectful program `f: (a: A) => F<B>` with a pure program `g: (b: B) => C` by lifting `g` to a function `lift(g): (fb: F<B>) => F<C>` provided that `F` admits a functor instance
+
+| Program f | Program g    | Composition   |
+| --------- | ------------ | ------------- |
+| pure      | pure         | `g ∘ f`       |
+| effectful | pure (unary) | `lift(g) ∘ f` |
+
+However `g` must be unary, that is it must accept only one argument as input. What if `g` accepts two arguments? Can we still lift `g` by using only the functor instance? Well, let's try!
+
+# Currying
+
+First of all we must model a function that accepts two arguments, let's say of type `B` and `C` (we can use a tuple) and returns a value of type `D`
+
+```ts
+g: (args: [B, C]) => D
+```
+
+We can rewrite `g` using a technique called **currying**.
+
+> Currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, **each with a single argument**. For example, a function that takes two arguments, one from `B` and one from `C`, and produces outputs in `D`, by currying is translated into a function that takes a single argument from `C` and produces as outputs functions from `B` to `C`.
+
+(source: [currying on wikipedia.org](https://en.wikipedia.org/wiki/Currying))
+
+So we can rewrite `g` to
+
+```ts
+g: (b: B) => (c: C) => D
+```
+
+What we want is a lifting operation, let't call it `liftA2` in order to distinguish it from our old `lift`, that outputs a function with the following signature
+
+```ts
+liftA2(g): (fb: F<B>) => (fc: F<C>) => F<D>
+```
+
+How can we get there? Since `g` is now unary, we can use the functor instance and our old `lift`
+
+```ts
+lift(g): (fb: F<B>) => F<(c: C) => D>
+```
+
+But now we are stuck: there's no legal operation on the functor instance which is able to **unpack** the value `F<(c: C) => D>` to a function `(fc: F<C>) => F<D>`.
+
+# Apply
+
+So let's introduce a new abstraction `Apply` that owns such a unpacking operation (named `ap`)
+
+```ts
+interface Apply<F> extends Functor<F> {
+  ap: <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>
+}
+```
+
+The `ap` function is basically `unpack` with the arguments rearranged
+
+```ts
+unpack: <C, D>(fcd: HKT<F, (c: C) => D>) => ((fc: HKT<F, C>) => HKT<F, D>)
+ap:     <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>
+```
+
+so `ap` can be derived from `unpack` (and viceversa).
+
+**Note**: the `HKT` type is the `fp-ts` way to represent a generic type constructor (a technique proposed in the [Lightweight higher-kinded polymorphism](https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf) paper) so when you see `HKT<F, X>` you can think to the type constructor `F` applied to the type `X` (i.e. `F<X>`).
+
+# Applicative
+
+Moreover it would be handy if there exists an operation which is able to **lift a value** of type `A` to a value of type `F<A>`. This way we could call the `liftA2(g)` function either by providing arguments of type `F<B>` and `F<C>` or by lifting values of type `B` and `C`.
+
+So let's introduce the `Applicative` abstraction which builds upon `Apply` and owns such operation (named `of`)
+
+```ts
+interface Applicative<F> extends Apply<F> {
+  of: <A>(a: A) => HKT<F, A>
+}
+```
+
+Let's see the `Applicative` instances for some common data types
+
+**Example** (`F = Array`)
+
+```ts
+import { flatten } from 'fp-ts/lib/Array'
+
+const applicativeArray = {
+  map: <A, B>(fa: Array<A>, f: (a: A) => B): Array<B> => fa.map(f),
+  of: <A>(a: A): Array<A> => [a],
+  ap: <A, B>(fab: Array<(a: A) => B>, fa: Array<A>): Array<B> =>
+    flatten(fab.map(f => fa.map(f)))
+}
+```
+
+**Example** (`F = Option`)
+
+```ts
+import { Option, some, none, isNone } from 'fp-ts/lib/Option'
+
+const applicativeOption = {
+  map: <A, B>(fa: Option<A>, f: (a: A) => B): Option<B> =>
+    isNone(fa) ? none : some(f(fa.value)),
+  of: <A>(a: A): Option<A> => some(a),
+  ap: <A, B>(fab: Option<(a: A) => B>, fa: Option<A>): Option<B> =>
+    isNone(fab) ? none : applicativeOption.map(fa, fab.value)
+}
+```
+
+**Example** (`F = Task`)
+
+```ts
+import { Task } from 'fp-ts/lib/Task'
+
+const applicativeTask = {
+  map: <A, B>(fa: Task<A>, f: (a: A) => B): Task<B> => () => fa().then(f),
+  of: <A>(a: A): Task<A> => () => Promise.resolve(a),
+  ap: <A, B>(fab: Task<(a: A) => B>, fa: Task<A>): Task<B> => () =>
+    Promise.all([fab(), fa()]).then(([f, a]) => f(a))
+}
+```
+
+# Lifting
+
+So given an instance of `Apply` for `F` can we now write `liftA2`?
+
+```ts
+import { HKT } from 'fp-ts/lib/HKT'
+import { Apply } from 'fp-ts/lib/Apply'
+
+type Curried2<B, C, D> = (b: B) => (c: C) => D
+
+function liftA2<F>(
+  F: Apply<F>
+): <B, C, D>(g: Curried2<B, C, D>) => Curried2<HKT<F, B>, HKT<F, C>, HKT<F, D>> {
+  return g => fb => fc => F.ap(F.map(fb, g), fc)
+}
+```
+
+Nice! But what about functions with **three** arguments? Do we need _yet another abstraction_?
+
+The good news is that the answer is no, `Apply` is enough
+
+```ts
+type Curried3<B, C, D, E> = (b: B) => (c: C) => (d: D) => E
+
+function liftA3<F>(
+  F: Apply<F>
+): <B, C, D, E>(
+  g: Curried3<B, C, D, E>
+) => Curried3<HKT<F, B>, HKT<F, C>, HKT<F, D>, HKT<F, E>> {
+  return g => fb => fc => fd => F.ap(F.ap(F.map(fb, g), fc), fd)
+}
+```
+
+Actually given an instance of `Apply` we can write a `liftAn` function, **for each** `n`.
+
+**Note**. `liftA1` is just `lift`, the `Functor` operation.
+
+We can now update our "composition table"
+
+| Program f | Program g     | Composition     |
+| --------- | ------------- | --------------- |
+| pure      | pure          | `g ∘ f`         |
+| effectful | pure, `n`-ary | `liftAn(g) ∘ f` |
+
+<center>where `liftA1 = lift`</center>
+
+# Is the general problem solved?
+
+Not yet. There's still an important case which is missing: what if **both** programs are effectful?
+
+Again we need something more: in the [next](./Monad.md) post I'll talk about one of the most important abstractions of functional programming: **monads**.
diff --git a/docs/getting-started/Category.md b/docs/getting-started/Category.md
@@ -0,0 +1,120 @@
+---
+title: Category
+parent: Getting started
+nav_order: 5
+---
+
+# Getting started with fp-ts: Category
+
+In the last posts we saw some basic abstractions used in functional programming: [Eq](../Eq.md), [Ord](../Ord.md), [Semigroup](../Semigroup.md) and [Monoid](../Monoid.md).
+
+In the next posts we will explore some advanced abstractions that make functional programming even more interesting.
+
+Storically the first advanced abstraction contained in [fp-ts](https://github.com/gcanti/fp-ts) is `Functor`, but before we can talk about functors we need to learn something about **categories** since functors are built upon them.
+
+A corner stone of functional programming is **composition**. But what does that exactely mean? When we can say that two things _compose_? And when we can say that things compose _well_?
+
+We need a **formal definition** of composition. That's what categories are all about.
+
+> Categories capture the essence of composition.
+
+# Categories
+
+The definition of category is a bit long so I'm going to split its definition in two parts:
+
+- the first is technical (first of all we need to define its constituents)
+- the second part will contain what we are most interested in: a notion of composition
+
+### Part I (Definition)
+
+A category is a pair `(Objects, Morphisms)` where:
+
+- `Objects` is a collection of **objects**
+- `Morphisms` is a collection of **morphisms** (or arrows) between the objects
+
+**Note**. The term "object" here has nothing to do with OOP, you can think of objects as black boxes you can't inspect, or even as some kind of ancillary placeholders for morphisms.
+
+Each morphism `f` has a source object `A` and a target object `B` where `A` and `B` are in `Objects`.
+
+We write `f: A ⟼ B`, and we say "f is a morphism from A to B".
+
+### Part II (Composition)
+
+There's an operation `∘`, named "composition", such that the following properties must hold
+
+- (**composition of morphisms**) whenever `f: A ⟼ B` and `g: B ⟼ C` are two morphism in `Morphisms` then it must exist a third morphism `g ∘ f: A ⟼ C` in `Morphisms` which is the _composition_ of `f` and `g`
+- (**associativity**) if `f: A ⟼ B`, `g: B ⟼ C` and `h: C ⟼ D` then `h ∘ (g ∘ f) = (h ∘ g) ∘ f`
+- (**identity**) for every object `X`, there exists a morphism `identity: X ⟼ X` called the _identity morphism_ for `X`, such that for every morphism `f: A ⟼ X` and every morphism `g: X ⟼ B`, we have `identity ∘ f = f` and `g ∘ identity` = g.
+
+**Example**
+
+<img src="./images/Category.png" width="300" alt="a simple category" />
+
+<center>(source: [category on wikipedia.org](https://en.wikipedia.org/wiki/Category_(mathematics)))</center>
+
+This category is quite simple, there are only three objects and six morphisms (1<sub>A</sub>, 1<sub>B</sub>, 1<sub>C</sub> are the identity morphisms of `A`, `B`, `C`).
+
+## Categories as programming languages
+
+A category can be interpreted as a simplified model of a **typed programming language**, where:
+
+- objects are **types**
+- morphisms are **functions**
+- `∘` is the usual **function composition**
+
+The diagram
+
+<img src="./images/Category.png" width="300" alt="a simple programming language" />
+
+can be interpreted as a fairly simple, immaginary programming language with only three types and a small bunch of functions.
+
+For example:
+
+- `A = string`
+- `B = number`
+- `C = boolean`
+- `f = string => number`
+- `g = number => boolean`
+- `g ∘ f = string => boolean`
+
+The implementation could be something like
+
+```ts
+function f(s: string): number {
+  return s.length
+}
+
+function g(n: number): boolean {
+  return n > 2
+}
+
+// h = g ∘ f
+function h(s: string): boolean {
+  return g(f(s))
+}
+```
+
+## A category for TypeScript
+
+We can define a category, named _TS_, as a model for the TypeScript language, where:
+
+- **objects** are all the TypeScript types: `string`, `number`, `Array<string>`, ...
+- **morphisms** are all the TypeScript functions: `(a: A) => B`, `(b: B) => C`, ... where `A`, `B`, `C`, ... are TypeScript types
+- **identity morphisms** are all encoded as a single polymorphic function `const identity = <A>(a: A): A => a`
+- **composition of morphisms** is the usual function composition (which is associative)
+
+As a model for TypeScript, _TS_ might seems too limited: no loops, no `if`s, _almost_ nothing... Nonetheless this simplified model is rich enough for our main purpose: reason about a well defined notion of composition.
+
+## The central problem with composition
+
+In _TS_ we can compose two generic functions `f: (a: A) => B` and `g: (c: C) => D` as long as `B = C`
+
+```ts
+function compose<A, B, C>(g: (b: B) => C, f: (a: A) => B): (a: A) => C {
+  return a => g(f(a))
+}
+```
+
+But what if `B != C`? How can we _compose_ such functions? Should we just give up?
+
+In the [next post](./Functor.md) we'll see under which conditions such a composition is possible. We'll talk about **functors**.