The common patterns

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

Monoid

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)

Nesting of pattern-matching

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
  • currying is a form of nesting (and capturing of free variables)
  • 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

Implicit nesting of curried (“multi-argument”) functions corresponds to an explicit nesting of chained calls to map on, lets say, Options (or Maybes).

Nesting implicitly establishes a particular (the only possible) order of evaluation within a non-strict language. (>>=) is implemented with nesting, just as (.) and (<=<). This is not an ancident. Nesting is a half of Lambda Calculus.

In short, a function composition (and currying) implies an /order, and nesting is the only way to establish it.

Ok, 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.

A sum-type

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.

Option

type 'a option = None | Some of 'a

Maybe

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

The functions on these types have the common form which directly reflect (mimics) the structure of the type. I will write them later.

“Errors” as just taking another branch

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.

Take another branch

We should think of what we call an “error” as just a signal to take another branch (backtrack and restart).

All the dramatic connotations must be removed. It is just a branch within a conditional expression.

This branch, however, which usually leads to “backtracking” and to a “restart” must always be included in a “plan” or a declarative program.

An error could be signaled in various ways, but the handling is uniform – just take (evaluate) the corresponding branch.

These exact notions are behind the Erlang uniform strategy of error handling. Understanding this is the beginning of “wisdom”.

Nothing was returned

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.

Returning Nothing is backtracking

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.

Nested maps

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”.

Combinators

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.