# Key Terminology

Last updated

Last updated

Read this entire walkthrough.

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 -> F<a>`

Often used to model side-effects in a program. Examples include:

`List<a>`

`Option<a>`

`Task<a>`

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.

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<b>`

`g: b -> c`

How can we compose `f`

and `g`

together? `lift`

ing is the process of taking `b -> c`

and creating `F<b> -> F<c>`

.

Which in turn lets us compose `a -> F<b>`

and `F<b> -> F<c>`

trivially as `a -> F<b> -> F<c>`

and ultimately `a -> F<c>`

.

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:

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:

Similarly, the `Maybe`

endofunctor has the form:

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.

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 typeA morphism of the form

`F<a> -> a`

, often called the evaluation function or the structure map

Once again, `Maybe`

is an example of an F-Algebra.

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.

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<C>) => F<D>`

.

Examples

`F = Array`

`F = Option`

`F = Task`

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.

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`

A trivial example of a semigroup for which `empty`

cannot be defined to satisfy the right and left identity laws.

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<a>`

`map: M<a> -> M<b>`

`get: M<a> -> a`

`concat: M<a> -> M<a> -> M<a>`

`flatten: M<M<a>> -> M<a>`

`flatMap: (a -> M<b>) -> (M<a> -> M<b>)`

**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

A is an `n`

-ary type operator taking as argument zero or more types, and returning another type. It has the type of signature: