Algebraic abstractions

A type is a Set of all possible values (may be an infinite Set).

Within this view a function \(f: A \rightarrow B\) is just a Set of Ordered Pairs which is a result of a Cartesian Product \(A \times B\) between Domain and Codomain.

A type is an instance of a particular class iff it implements a required set of type-signatures (an interface) for all values in a Set (and respects corresponding laws stated formally elsewhere).

Closure

\((S, \bigoplus)\), a Set S is closed under an operation \(\bigoplus\) iff \[\forall a, b \in S, a \bigoplus b \in S\]

A same-set (type-preserving) binary operation.

op :: a -> a -> a

Associativity is not required.

Semigroup

\((S, \bigoplus)\), an associative binary operation \(\bigoplus\) with a Closure property. Closure is implicit and “natural” due to multiple applications of the same operator, such that \[\forall a, b, c \in S, (a \bigoplus b) \bigoplus c = a \bigoplus (b \bigoplus c)\] Identity is not required.

An order-independent (in a chain) operation.

class Semigroup a where
  (<>) :: a -> a -> a

Monoid

\((S, \bigoplus, e)\), an associative operation which has an identity element e (value). Implicit closure or required by already being a Semigroup. \[x \bigoplus e = x = e \bigoplus x\] \[x \bigoplus (y \bigoplus z) = (x \bigoplus y) \bigoplus z\] An identity-preserving operation.

class Semigroup a => Monoid a where
  mempty  :: a

  mappend :: a -> a -> a
  mappend = (<>)
  -- This is not required, folding
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

Functor

A homomorphism (of the same form). Just like a Closure, but for “shapes” (forms).

h is a total function \(h: (N, E) \rightarrow (N', E')\), such that: \[\forall (A, B) \in E, \exists (h(A), h(B)) \in E\]

h is thus distributes over a structure, just like \(*\) over \(+\).

A higher-level structure-preserving transformation.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Can be an Endofunctor - a same-category operation.

Distributive

\(\bigotimes\) on \(S\) distributes over \(+\) on \(S\) if and only if \[\forall a, b, c \in S, a \bigotimes (b + c) = (a \bigotimes b) + (a \bigotimes c) \land (b + c) \bigotimes a = (b \bigotimes a) + (c \bigotimes a)\]

This is a property of a pair of operations \((S, (\bigotimes, \bigoplus))\).

Instances

Tuples

Distributive law (over a structure)

instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
  (a, b) <> (a', b') = (a<>a', b<>b')

Identity

instance (Monoid a, Monoid b) => Monoid (a,b) where
  mempty = (mempty, mempty)

First comes from a “defining Set” (in a Cartesian Product), a function can be viewed as a Set of Ordered Pairs.

Assuming this is an ordered (by the first element) Pair \(x -> y\), part of a function space (image).

instance Functor (,) where
  fmap f (x, y) = (x, f y)

So this is equivalent to mapping f over the result of \(x -> y\).

An applicative is always a mess. Values merge with (<>) and a function applied.

instance Monoid a => Applicative ((,) a) where
  pure x = (mempty, x)
  (u, f) <*> (v, x) = (u <> v, f x)
  liftA2 f (u, x) (v, y) = (u <> v, f x y)

Functions

A function is viewed as a “container” for its result.

instance Functor ((->) r) where
    fmap = (.)

Maybe

Distributive law (over a structure)

instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> b       = b
    a       <> Nothing = a
    Just a  <> Just b  = Just (a <> b)

the Identity element

instance Semigroup a => Monoid (Maybe a) where
    mempty = Nothing

Empty | non-empty aspect of a List. Two distinct data-constructors. It is not a recursive structure.

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

Propagating Nothingness (emptiness), distributing f over

Lists

Concatenation is, indeed, associative, and the empty list is an orthogonal to it.

instance Semigroup [a] where
  (<>) = (++)

With [] it will form a Monoid.

instance Monoid [a] where
  mempty  = []
  -- This is not required, folding
  mconcat xss = [x | xs <- xss, x <- xs]