Algebraic abstractions

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

Within this view a function $f : A \to 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, ⨁)$ , a Set S is closed under an operation $⨁$ iff $\forall a, b \in S, a ⨁ b \in S$

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

op :: a -> a -> a

Associativity is not required.

Semigroup

$(S, ⨁)$ , an associative binary operation $⨁$ 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 ⨁ b) ⨁ c = a ⨁ (b ⨁ c)$ Identity is not required.

An order-independent (in a chain) operation.

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

Monoid

$(S, ⨁, e)$ , an associative operation which has an identity element e (value). Implicit closure or required by already being a Semigroup. $x ⨁ e = x = e ⨁ x$ $x ⨁ (y ⨁ z) = (x ⨁ y) ⨁ 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) \to (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

$⨂$ on $S$ distributes over $+$ on $S$ if and only if $\forall a, b, c \in S, a ⨂ (b + c) = (a ⨂ b) + (a ⨂ c) \land (b + c) ⨂ a = (b ⨂ a) + (c ⨂ a)$

This is a property of a pair of operations $(S, (⨂, ⨁))$ .

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]