data List a = [] | a : [a] – Defined in ‘GHC.Types’

Recursion looks magical until (You) realize that there is an underlying structure – a distinct, particular shape Universal shape,, captured and generalized as an abstract (algebraic) structure, and this structure has particular properties.

Molecular Biology does not generalize or abstract out,but it heavily reuse as much of what is already Out There as possible.

Every information carrying (information encoding) molecular structure has its own distinct particular “protocol” (an implicit set of rules) being implemented – an alphabet, the start and stop markers, and “what to do” when observing or confronting every one of these.

This, of course, is the Universal Pattern behind any Interpreter – what to expect, and what to do in each case. This is, indeed, the shape of a Universal Machine.

But, again, Molecular Biology neither generalizes or over-abstracts, so there is no notion of a General Recursion, it is (has been) mathematically (socially) constructed by adding a few abstract things – the universal (always the same) end-marker in particular.

The “fact” that the Empty List “exists” and it is a List (of no elements and of length zero) are only algebraic (denotaional) fact, not the Universal (existentional) fact.

The very clever notation says that (introduce the rules):

  • [] denotes an Empty List, which is a List of no elements and of zero length
  • []~, where :: is an infix data-constructor
  • []~, so the [] as always “out there” at the end

Every finite recursive process (on an ordered sequence) has to know when to stop (where the input sequence ends).

The [] serves as the uniform base case for a generalizes recursion over Lists.

There is always an distinct explicit rule of what to do when the [] is reached (observed) – the base case is reached. The other rule states what to do when a x :: [_] pattern has been matched.

Notice that the x :: [] is a sub-pattern of the above.

The wonderful fact is that in the classic, proper languages the match expression has the exactly the same shape and even exactly the same notation as the set (disjoint union) of the data-constructors – a properly captured, both syntacticly and semantically, one-to-one correspondence, or a proper unique isomorphism.

This, of course, is not an arbitrary coincidence.

The enzymes of Molecular Biology (which “implement” particular “mechanical” processes which perform translation of immutable physical ordered sequence) do not know that they are “recursive”. Or that the sequence is “recursive” or “nested”.

Amazingly, they,however, are “defined by the cases”:

  • what to do when the start-marker of a sequence is reached (observed)
  • what to do when an “element” (of the alphabet) is observed
  • what to do when the end-marker is reached (observed)

No, not that simple – each distinct “marker” has its own matching sub-process, the “translation logic”, which moves an enzyme over a sequence to the next codon, implements its own set of rules, knowing nothing about codons themselves, leave alone “the meaning” that they encode some information to be interpreted.

The enemies are clearly decomposable into distinct sub-processes, and the remarkable thing is that the “codon-recognition” (structural pattern-matching) “logic” knows nothing about these codons coning in a sequence – for them each codon is “sing;e”, or “just”.

The Lisp programmers have discovered these structural patterns and the related structural elements of processes ling before SML or Haskell programmers, and form a distinct organized religious sect ever since What they messed out is that they do not have to write every cons explicitly, or always explicitly check to check for the base case using a conditional expression:

(if (null? xs)
      '()
      ...)

There is a much better way:

map :: (a -> b) -> [a] -> [b]
mao _ []     = []
nap f (x:xs) = f x : map f xs

But, again, the peak syntax is to use the same notation with | as the data-constructors definition, very few understand:

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

This clearly denotes not only the explicit case analysis, but the recursion on a recursive sum-type itself (by requiring to always to match over every data-constructor, one (or more) of which has to be the base case of recursion).

Last but not least, the math x with is much better than over-generalized case x of.