# Key Terminology Read this entire walkthrough. {% embed url="" %} #### Type / Category A type is a mathematical concept referring to a category, in lay-speak. The more formal idea of a category is better defined as: * Consistent groupings of **objects** * Certain transformations between those groupings, known as **morphisms** An **object** may also be a **morhphism**, this is where **Functors** come in. #### Function Denoted as `f(a)` Defines a mapping between types, taking the form: `f: a -> b` Where `a` is the input type and `b` is the output type. #### Algebra An algebra is a family of functions with the signature `f: a -> a` for a given category `a`. #### Type Constructor A [type constructor](https://en.wikipedia.org/wiki/Type_constructor) is an `n`-ary type operator taking as argument zero or more types, and returning another type. It has the type of signature: `a -> F` Often used to model side-effects in a program. Examples include: `List` `Option` `Task` #### Catamorphism A catamorphism is a generalised morphism concept that performs an operation known as `fold` or `reduce`. The name comes from the Greek 'κατα-' meaning "downward or according to". A useful mnemonic is to think of a catastrophe destroying something. {% embed url="" %} #### Functor A type constructor is classed as a Functor if the `lift` operation can be defined for it. To avoid further confusion let it be clear that `lift`, `map` and `fmap` can be conceptually considered equivalent. Say we have: `f: a -> F` `g: b -> c` How can we compose `f` and `g` together? `lift`ing is the process of taking `b -> c` and creating `F -> F`. Which in turn lets us compose `a -> F` and `F -> F` trivially as `a -> F -> F` and ultimately `a -> F`. A more complete way to define a Functor is that it is made up of two aspects: * `A type constructor F:` a **mapping between objects** that associates to each object `X` in *a* an object in *b* * `A function lift:` a **mapping between morphisms** that associates to each morphism in *c* a morphism in *d* Examples: ```fsharp let lift (g: b -> c) (fb: List) = fb |> List.map g ``` ```typescript function lift(g: (b: B) => C): (fb: Array) => Array { return fb => fb.map(g) } function lift(g: (b: B) => C): (fb: Option) => Option { return fb => (isNone(fb) ? none : some(g(fb.value))) } function lift(g: (b: B) => C): (fb: Task) => Task { return fb => () => fb().then(g) } ``` {% embed url="" %} #### Endofunctors An endofunctor is a functor mapping to and from the same category, `F: C -> C.` The simplest example of an endofunctor is `id` which has the signature `a -> a`. We can define the identity endofunctor as: ```fsharp module Identity = // ('a -> 'b) -> Identity<'a> -> Identity<'b> let map f (Identity x) = Identity (f x) ``` Similarly, the `Maybe` endofunctor has the form: ```haskell instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x) ``` If unclear, the defining property that makes a functor an endofunctor above is that `fmap` always preserves the category, which is not necessarily true for a functor. {% embed url="" %} #### F-Algebra Building on the base idea of an algebra, an F-Algebra is composed of three things: * An endofunctor `F` * An object `a` that is "inside" the endofunctor as the carried type * A morphism of the form `F -> a`, often called the evaluation function or the structure map Once again, `Maybe` is an example of an F-Algebra. ```haskell data MaybeF a c = NothingF | JustF a deriving (Show, Eq, Read) instance Functor (MaybeF a) where fmap _ NothingF = NothingF fmap _ (JustF x) = JustF x ``` {% embed url="" %} #### Semigroup A semigroup is a pair `(A, *)` in which `A` is a non-empty set and `*` is a binary **associative** operation on `A`, i.e. a function that takes two elements of `A` as input and returns an element of `A` as output. Effectively, this means that the `concat` morphism can be defined. ```typescript interface Semigroup { concat: (x: A, y: A) => A } const semigroupProduct: Semigroup = { concat: (x, y) => x * y } const semigroupSum: Semigroup = { concat: (x, y) => x + y } const semigroupString: Semigroup = { concat: (x, y) => x + y } ``` #### Applicative Functors A Functor is classed as Applicative if the `apply` morphism can be defined for it, these are also simply known as Applicatives for short. In practical terms this property allows us to handle `n-ary` Functors rather than just `unary`. `apply` as an operation on the functor instance `F` is able to **unpack** the value `F<(c: C) => D>` to a function `(fc: F) => F`. Examples `F = Array` ```typescript import { flatten } from 'fp-ts/lib/Array' const applicativeArray = { map: (fa: Array, f: (a: A) => B): Array => fa.map(f), of: (a: A): Array => [a], ap: (fab: Array<(a: A) => B>, fa: Array): Array => flatten(fab.map(f => fa.map(f))) // flatten prevents [['a']] style output } ``` `F = Option` ```typescript import { Option, some, none, isNone } from 'fp-ts/lib/Option' const applicativeOption = { map: (fa: Option, f: (a: A) => B): Option => isNone(fa) ? none : some(f(fa.value)), of: (a: A): Option => some(a), ap: (fab: Option<(a: A) => B>, fa: Option): Option => isNone(fab) ? none : applicativeOption.map(fa, fab.value) } ``` `F = Task` ```typescript import { Task } from 'fp-ts/lib/Task' const applicativeTask = { map: (fa: Task, f: (a: A) => B): Task => () => fa().then(f), of: (a: A): Task => () => Promise.resolve(a), ap: (fab: Task<(a: A) => B>, fa: Task): Task => () => Promise.all([fab(), fa()]).then(([f, a]) => f(a)) } ``` {% embed url="" %} #### Monoid A `Monoid` is any `Semigroup` that happens to have a special value which is "neutral" with respect to `concat`. Do note, not all Semigroups are Monoids. ```typescript import { Semigroup } from 'fp-ts/lib/Semigroup' interface Monoid extends Semigroup { readonly empty: A } ``` The following laws must hold * **Right identity**: `concat(x, empty) = x`, for all `x` in `A` * **Left identity**: `concat(empty, x) = x`, for all `x` in `A` ```typescript /** number `Monoid` under addition */ const monoidSum: Monoid = { concat: (x, y) => x + y, empty: 0 } /** number `Monoid` under multiplication */ const monoidProduct: Monoid = { concat: (x, y) => x * y, empty: 1 } const monoidString: Monoid = { concat: (x, y) => x + y, empty: '' } /** boolean monoid under conjunction */ const monoidAll: Monoid = { concat: (x, y) => x && y, empty: true } /** boolean monoid under disjunction */ const monoidAny: Monoid = { concat: (x, y) => x || y, empty: false } ``` #### **Non-Monoidal Semigroup** A trivial example of a semigroup for which `empty` cannot be defined to satisfy the right and left identity laws. ```typescript const semigroupSpace: Semigroup = { concat: (x, y) => x + ' ' + y } ``` {% embed url="" %} #### Monad A Monad is simply a Monoid in the category of Endofunctors 🙃. What this practically means is that we can define the operations: * `of: a -> M` * `map: M -> M` * `get: M -> a` * `concat: M -> M -> M` * `flatten: M> -> M` * `flatMap: (a -> M) -> (M -> M)` #### #### **Pending questions to directly address**: * how does `filter` fit in? * define transducers * draw a diagram of related terms * how does a catamorphism interact with the definitions of semigroup, monoid and monad? * what is the **common** set of useful morphisms? * map * get * concat * bind / chain / of(?) * apply * fold * unfold --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://notes.bf.wtf/programming/functional-programming/key-terminology.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.