What I love the most.

Let's sort out some overhyped bullshit.

Optional Value

This is an attempt to formalize the general notion of absence, of nothing instead of something, of an empty slot. In the world of enzymes there could be a slot for a protein, which might be empty or filled with a certain protein (actually a certain pattern of a bigger structure).

This notion is related to the mathematical (abstract) notion of zero, denoted by the symbol 0. In math a zero could be obtained by f(x) = x - x, however in reality if something is not (or no longer) there, it is just no longer there. There is no notion of 0 of every possible particles or other similar abstract nonsense.

Same, BTW, goes to negation. NON-apple makes no more sense than zero apples. However, not apples (except apples) makes sense.

In the languages of DNA transcription there is, obviously, no 0 (Notion of nothingness requires an intelligent observer which is absent). Empty slot in an enzyme is just an empty slot, it is not a state of zero or all that crap. Emptiness is concrete, nothingness is abstract.

data  Maybe a  =  Nothing | Just a

Which must be rather Empty | Contains a.


This an attempt to formalize the general notion of grouping (combining pieces, say drops of water, together).

The notion of Semigroup is to have an associative binary operation (<>) such that it confirms to the Associativity Law, which means that order of operations does not matter. (1 + 3) + 5 = 1 + (3 + 5). Addition for Numbers (+) is an associative operation. So is concatenation for Lists (++). [1,3] (++) [5] = [1] (++) [3,5]. Cons, however, is not.

the Associativity Law in pseudocode:

x <> (y <> z) = (x <> y) <> z

where a generic associative function (<>) has the type

(<>) :: a -> a -> a

Which means it produces a new value of the same type, by combining two values

Let's state it in plain English: to be a Semigroup is to have an associative binary operation defined and to have a concatenation (merging into one) function in terms of this associative operation. It could be the same function, like the binary (+) for Numbers and the binary (++) for Lists.

Addition is an example of an associative operation (conforms to the Associativity Law)

x + (y + z) = (x + y) + z

where + is a binary combinator. Binary stand for arity of 2. It requires exactly two arguments. No more, no less.

For addition, due to the abstract nature of numbers, the order of arguments of binary operation (+) does not matter - 1 + 2 = 2 + 1 while for lists [1, 2] is not the same as [2, 1], because Lists have a concrete ordered structure which Numbers or Sets lack.

This is the notion that adding Hydrogen to Hydrogen-and-Oxygen is the same as adding Hydrogen-and-Oxygen to another Hydrogen.

Reduction of an aggregate

Reduction is application of a combinator to an aggregate. Some enzymes could be viewed as combinators (reducers), while most of them are mappers (transducers).

Reduce a list of numbers with +

(+ 1 2 3 4)

reduction applied to nothing is identity (the notion of having no effect)



There is also notion of concatenation (merging together into one) associated with a Semigroup.

In typed lambda calculus it is required to define the notion of NonEmpty which basically means material, existing, because concatenation of something cannot be nothing and in order not to blow up combinators applied to the elements of an aggregate (as if aggregates of the Nature MUST ALWAYS BE homogeneous!).

Concatenation is an instance of reduction (arithmetic addition could be viewed as concatenation for a List of numbers).

sconcat :: NonEmpty a -> a
sconcat (a :| as) = go a as where
      go b (c:cs) = b <> go c cs
      go b []     = b

sconcat stands for semi-group concatenation, (:|) stands for cons to NonEmpty.


Monoids are semi-groups with identity (having no effect) and emptiness (nothing).

Monoid Laws in pseudocode

  • adding nothing produces no effect, order of operations does not matter
    x <> mempty = x
    mempty <> x = x
    mempty incidentally (unintentionally) beautifully stands for Marked (tagged) Empty, because there is no such thing as nothing in Nature.
  • semi-group law (Associative Law)
    x <> (y <> z) = (x <> y) <> z
  • concatenation (merging into one)
    mconcat = foldr (<>) mempty

Notice that beside the notion of grouping only abstract notions of Sum (addition) and Product (multiplication) corresponds to (form a) Monoid.


Set is a formalized notion of a group of abstract entities, originally defined on Numbers. It implies notion of membership (inclusion) and does not have the notion of ordering and hence duplicate values. (Each instance of a Number is referred to the same Number - there is no duplicates among Numbers).

A set might be empty or contain arbitrary values, including other sets, unrestricted to be homogeneous. The only notion is of membership, which is defined as a set of operations on elements (addition, check-for-membership, removal of an element).

At a higher level of abstraction a Set could be viewed as a Iterable or even Traversable, but the order of elements selected is arbitrary. Each element must be selected exactly once.


A List is a possible empty "concrete" ordered sequence, may include arbitrary items, including duplicates.

Homogeneous Lists

Only Homogeneous Lists are instances of Monoid (while NonEmpty homogeneous List is an instance of a Semi-Group).

This is exactly the place where the glimpse of bullshit is caught for the first time - the whole thing is defined only for homogeneous lists, and associativity is defined only for NonEmpty homogeneous lists (because it has been modelled on numbers, and numbers are not real).

To put it simply - all this hierarchy of abstract crap is just artificially imposed mental construct. All this formalism is applicable only to abstract numbers and other restricted homogenous abstract concepts, not to "concrete" atoms or processes of reality.

Nevertheless this formalism is occasionally useful in typed lambda calculus because it help caught type mismatches in function application.

The whole thing

The basic notions

  • Grouping (combining) append = <> using an associative operation (<>) (a combinator)
  • Reduction (folding) using a combinator <>
    • Concatenation (merging) concat = fold <> []
class Semigroup a where
        (<>) :: a -> a -> a

        sconcat :: NonEmpty a -> a
        sconcat (a :| as) = go a as where
          go b (c:cs) = b <> go c cs
          go b []     = b

        stimes :: Integral b => b -> a -> a
        stimes = stimesDefault
class Semigroup a => Monoid a where
        mempty  :: a

        mappend :: a -> a -> a
        mappend = (<>)

        mconcat :: [a] -> a
        mconcat = foldr mappend mempty
instance Semigroup [a] where
        (<>) = (++)

        stimes = stimesList
instance Monoid [a] where
        mempty  = []
        mconcat xss = [x | xs <- xss, x <- xs]

Non-empty list

instance Semigroup (NonEmpty a) where
        (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs)
instance Semigroup b => Semigroup (a -> b) where
        f <> g = \x -> f x <> g x
        stimes n f e = stimes n (f e)

Maybe forms a Semigroup, why not?

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

    stimes = stimesMaybe

Folding (reduction)

Folding is a generalized reduction [of a structure to a single value], given a binary combinator and initial value (mempty or identity)

Folding implies a structure. A Traversable structure. To traverse a structure means to visit (to select) each element of it exactly once.

A single value can be traversed, a linear structure, a tree, an acyclic graph is traversable, general graph (a network) is not traversable. An empty structure is traversable.

So, Foldable implies Traversable, and a folds are just a family of high order functions.

The accompanying metaphor is the process of folding of something spread into something folded.

class Foldable (t :: * -> *) where
  foldr :: (a -> b -> b) -> b -> t a -> b

Mapping (transformation)

Functor is a formalization of the notion of mapping over everything which could be mapped over. List is an obvious example.

Mapping is a generalized notion of uniformly transforming each element of a structure (in the same way) given a function on elements. The structure is kept intact and completely encapsulated from the function on elements.

The metaphor is that a function does not know that it is used on aggregates.

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

specialized (implemented) for Lists []

map :: (a -> b) -> [a] -> [b]   

What is the point of classifying the classic map as a Functor? None. Except when you are an academic and getting paid for discussing higher pure abstractions.

What is more interesting is that map0 could be expressed in terms of foldr

(define map (lambda (f xs)
                (foldr (lambda (x xs) (cons (f x) xs)) '() xs)))

which means that we could map over everything which is Foldable.


class Functor f => Applicative (f :: * -> *) where
  (<*>) :: f (a -> b) -> f a -> f b
Last modified 2 years ago Last modified on Dec 7, 2017, 9:43:38 AM
Note: See TracWiki for help on using the wiki.