Okay, what are the most fundamental, non-bullshit mathematical notions for Functional Programming?

  • Lambdas, Functions, Currying and Partial Application
  • The algebraic notion of a Products and their representation as tuples
  • an Ordered Sequence as a Universal shape
  • Recursive/Nested data structures, especially a List and a Tree
  • Recursive processes (of nested function calls) which arise naturally over recursive data structures.
  • The Duality of an Initial Algebra and an Interpreter (being a Unique Homomorphism)

It is not a random coincidence that arguments of a multi-argument function (before Currying) are tuples, not Lists (except in LISPs).

Currying “emerges naturally” when we list all the “individual morphisms” and observe that a \(B \rightarrow C\) is isomorphic to (has the same structure as) \(C^B\) (as many and the same arrows).

It goes like this: \(A \times B \rightarrow C\) is isomorphic to \(A \rightarrow C^B\), but \(C^B\) is just \(B \rightarrow C\), so \(A \rightarrow (B \rightarrow C)\). Isomorphic here means that so-called Hom Sets (sets of all arrows) have the exactly same elements, which means they are the same set. The Category Theory does not say “the same”, because that would mean the same “object”, which is not the case, it say “isomorphic” to each other.

\(Hom(A×B,C)≅Hom(A,B→C)\).

This is a non-bullshit part.

Why Products? Well, single atoms (or single aminoacids) are way too boring. It gets interesting when chains emerge. Products capture the notion of a molecule. Ordered sequence of a fixed size is what tuples are, and they perfectly capture the notion of a chain of aminoacids – a polypeptide – which is of a fixed size and contains different kinds of aminoacids in a particular order).

Notice that a single strand of DNA or a single mRNA is a List (due to an arbitrary length), but a protein is definitely a Tuple.

And the whole DNA -> mRNA -> amino acids -> proteins -> enzymes is nothing but information processing, while enzymes are “pure mechanical functions” (same inputs – same output, always), at least in theory.

So, what if we want to pass around and, especially, return more than one value, something which has “more structure”?

The answer is – a Product, and for us, programmers – a tuple.

Not take a deep breath – here comes another aha-moment – it is not a Monad that is the most primitive and fundamental notion (after the Lambda itself), but passing tuples around, especially between recursive calls, when a function calls itself.

A Monad just an generalized abstract interface, which can be used to make the passing of the “second value” implicit. The composition function [itself] gets redefined and it does all the different dirty jobs. That is all.