The recurring patterns captured as a Monoid

There are recurrent patterns, which has been captured in familiar “standard” abstractions.

A Set along with a composition operation, which has an identity element.

• addition, for (+) identity is 0
• concatenation, which is a specialization of putting together, identity is "".
• List, a fundamental recursive sum-type, identity is []
• Option, a specialization of empty/non-empty aspect of a List, identity is None
• Boolean logic, very subtle, identity is False (false imply nothing)

The notion that some Boolean operations form a Monoid is very subtle, but it will emerge with conditional expressions.

For AND we have False as the identity element (a single False). For OR it is True (at least one True)

It takes some effort to disentangle and clearly separate all the notions and “patterns” involved, but once it is done, everything is clear and self-evident.

There are notions involved:

• the universal notion behind function composition is nesting.
• the universal notion of pattern-matching on data-constructors of sum-types
• one and only one branch will be evaluated
• sum-types (the data-constructors) can be parameterized

The main principle is this: functions defined by clauses are composed branch-wise.

The “natural” pattern-matching on data-constructors (“variants” or possible outcomes) results in functions defined with clauses (like abs in mathematics).

These clauses reflect the “structure” of the type and the commonalities will be noticed and abstracted out. Some clauses (or branches) will be common, or even identical.

When composed (or nested) each branch will be composed with the corresponding one, and this “branch-wise composition” will form a distinct “path” within the whole “composition” (a chain of nested map or whatever).

The clear view is this. Functions defined by clauses (or distinct branches of the match expression) can only be composed at the corresponding branch level, thus forming distinct “patches” within.

Each “path” or a composed branches (one and only one of which will be evaluated) is its own level of abstraction within composed functions defined by clauses.

Once your type has more than one data-constructor we naturally pattern-match on them, and all the functions or expressions would have the particular form of the type, which reflects (mimics) its “structure”.

Any function would “naturally” have as many clauses as there are data-constructors. So would have a match expression.

The common pattern is captured with pattern-matching – for the case of the identity element of a Monoid the value just propagates – being passed along “untouched”, and the other branch will not be evaluated.

The mathematical notion is that the identity element of an operation do nothing (literally), this is why it just being passed along within its branch.

type 'a option = None | Some of 'a

type Maybe :: * -> *
data Maybe a = Nothing | Just a

There is a universal notion of a condition, captured by the IF special form – with at least two potential outcomes, while one and only one branch (the actual next step) could be actually taken. The other branch will remain as an ephemeral potentiality, and will never be “seen” in the actual “path” (a sequence of steps) of a process.

Pattern-matching on data-constructors of a sum-type (a tagged-union of potential outcomes) generalizes IF (the short-circuiting conditional expression).

The fundamental property is, again, that one and only one branch will actually be taken (evaluated) and the others will “disappear”, as never existed, but as ephemeral potentialities or imaginary possibilities.

Yes, we as humans are conditioned to thing in terms of a “fork on the road”, and where the each way is no less real as the other. This is how we miss the subtle fact that, possiblel outcome and an actual outcome (the next step being taken) live at very different levels of abstraction and must never be “mixed”.

The clear separation between potential (or possible) and actual (taken) is the mark of mature thinking.

So, when nothing (meaningful) was returned, we have to evaluate a corresponding branch, which must always be present.

None or Nohing thus is an identity element of a Monoid of composition (chain) of actions without an error occured, /yet.

Once the “Nothing” branch has been evaluated, it will just propagate along, and all the other branches (in a chain) will remain evaluated.

Thus no further steps will be taken by a process along the “happy” path.

When we take the “Nothing” branch we simply backtrack (literally, through the call-stack) to a function where a restart (if any) could have occur.

The genius Erlang guys have noticed and generalized this universal pattern with the supervision hierarchies. The process “fail” and the failure propagaget to the “supervisor” which restart a new process.

So, we nest (which is the same as compose) the map function over Option or Maybe types.

This is how we compose computations which may fail at any step. They have the common “fail branch”, which is of “Nothing” (to return).

flatMap composes “Kleisli arrows”.

There is a small set of combinators that can be composed with map or flatMap.

Some of these functions are non-strict (lazy) on its arguments, so they short-circuit, just like the IF special form does.

The most familiar are orElse and andThen.