Let’s try to re-build the foundation of Pure Functional programming in a lazy language such as Miranda or Haskell from the first principles.
Despite nearly 30 years of research and thousands of academic papers every real world Haskell project is a fucking mess of over-abstraction, using the latest meme abstraction or a fad of the day, whike the whole field is an endless contest of “look, ma, I am so smart” academic papers. The Arrows paper, and preceding Monad Transformers papers are the hallmarks of academic penis size contests.
So, let’s try to rebuild everything we can from the first principles, right from the ground up.
The Haskell 98 report and the Library report was, in a sense, an arrival at the promised land. All the good books of the time, including Functional Approach To Programming, Bird and Wadler book on Miranda, and every single other book in the late 90s and early 2000s preached the enlightenment of purity and doing thing Just Right, the optimal way, in Just A Few Lines Of Code.
That promise seem to never materialize, what we have got shit like Conduit, Yesod or whatever it is. What we have arrived at instead is a towering hierarchies of J2EE-like patterns encoded in Monadic contexts, and competition of whose Arrow is longer and thicker.
Let’s start from the absolute foundation. We have the Simple Typed Lambda Calculus, which not just Turing Complete (when we extend it with recursion), but uses the type system to avoid paradoxes related to academic fancies of the Set Theory (that every set is a subset of itself, and is thus included in the set of all subsets of itself, which is, of course, bullshit in order to have nice definitions).
The Lambda Calculus is also, by definition and by construction, a lazy (non-strict) system (language), so all the nice properties of laziness are Out There from the start.
We have Abstraction (as Gentzen’s Introduction rule) and Application (as Elimination rule), variable bindings, parameter passing, returning of a value, nesting of function calls (application), recursion, which is also nesting of function calls, proper lexical scope, and currying and partial application all arise naturally.
We then extend the Lambda Calculus by adding Sum and Product types, as well as proper Function Types (as categorical morphisms) into the language as built-ins and thus, indeed, have approached the promised land re be reborn in and the nirvana of doing things “Just Right”.
The only one fundamental problem is still here. Since the only way to establish a particular (Causal) order of evaluation in a lazy language is explicit nesting of function calls (which is what both function composition and recursion do), do not have a universal, standardized way to use data-dependency between nested calls, and cannot pass a static or mutable state to a nested function.
Notice that recursion is operationally the same as function composition – it is nesting of function calls.
According to Barbara Liskov, however, everything can be solved by the Abstraction by Parameterization principle, which basically means pass another parameter along, which may be an implicit one (as in Scala), may be a dictionary (as in Haskell), maybe as a closure, or a higher-order function, which is a closure.
Another fundamental principle is Abstraction By Specification (also Liskov), so we have to have standardized abstract interfaces, and just pass around implementations as higher order functions.
Iterators (and the generalized notion of a Protocol as an implemented set of rules) was the culmination and triumph of this approachf Passing closures which implement a particular protocol is the pattern which emerges long before they knew how to say “Dependency Injection”.
Haskell does not have iterators, but it has its lazy lists (being also, by construction, lazy streams), so, basically they are implicitly iterators.
Then Functional Design patterns of Scott Wlaschin was another attempt to summarize the actual patters used in functional programming, and what he came up with was Functions, Functions and Functions.
But long before Wlaschin, back in 90s, Peter Norvig wrote an essay saying just the same – everything you have in your imperative OO crappy languages are just patterns of high-order functions. Google it.
Now let’s see which standard abstract interfaces we have.
- a function application ($)
- a function composition (.)
- a Mealy machine
- a Monad
Despite all the bullshit written about Monads, they are, indeed, arise naturally within the Category Theory and thus are inevitable. The universal notion behind the monadic interfaces is of a Kleisli arrow, which is a mapping (an ordinary pure function) but that “crosses an abstraction barrier” by enhancing the range of a function.
To be more precise, it maps a pure value into some larger algebraic structure than just a value. Product, being the “smallest” larger algebraic structure possible, while a Functor is a generalization of a “larger” algebraic structure (which is not necessarily a Product). Again, these notions arise naturally just from construction and observations, and thus are inevitable.
I will argue that we do not have to have a Functor as the target structure, a product is good-enough, but Functor is “nice to have”, since it abstract out the actual algebraic “shape” or form.
Now we can do the same trick with the domain, by having a larger algebraic structure for every element of the domain. This, I suppose, is exactly what a Natural transformation between categories supposed to capture – mapping the whole type (well, Category) into an isomorphic type (Category) with every value being embedded into some large algebraic structure, of which Product is the minimal and the most fundamental.
The confusion arise because a Functor can be defined as mapping of whole types, and also between types, which the original algebraic structure is preserved and no information is ever being lost, but the range can uniformly enhance or transform (translate) the structure, without breaking or changing any existing relations only introducing new ones.
This abstract view is just generalization of DNA translation machinery, which does exactly this – never breaks existing structure, adds more structure and nests these operations (steps).
The Kleisli arrows, by the way, are exactly the ones between different structural shapes of the domain and codomain, each individual morphism is such a Kleisli arrow, and each pair of values have a simpler value as source and value with some additional structure as the target.
Notice that nothing else ever happens, just this. Monads, thus, indeed arise naturally, but the syntax and the interfaces chosen by the Great Bearded Guys at Haskell committee can be better.
We have the fish operator, but it requires even more wrapping.
At the level of the Category Theory (arrows between dots) everything is justified and optimal and complete and Inevitable, the problem is how do we represent and implement such composition in Haskell.
Instead of trying to summarize the last 30 years of academic papers and code, we can try to find the only optimal way to solve the passing additional state or data dependencies between nested function calls.
It seems like just using Products us enough for everything and can even be proved so.
We want only one thing from the Arrow framework – the idea of introducing the (->) morphism as a higher order function, which wraps an ordinary function.
The principal idea is to lift the whole function type (A -> B -> C), which includes the domain type and the range type into a “richer Category”, where composition is exactly the same, but the Domain and Range types are being enhanced (they call this lifted ) or uniformly translated into richer algebraic structures. And the whole new set of morphisms will naturally compose.
There are many patterns: what to do with, what to store in, when to modify and when to pass along the data in the “larger” Products, and we have to list all the common possibilities and try to generalize and arrive at the only optimal set of interfaces the smallest set of combinaters.
That won’t be a universal machine, but universal Recursive machine, which acts on linear sequences – every recursive computation can be expressed with it. But since almost everything in a pure functional lazy language is nesting of function calls (the implicit dependency graph they form), a lot can be done.
And, of course, the key a-ha moment is that implementations of Mealy Machine, State Monad and some Arrow combinators are structurally the same transition, and this can be properly generalized, stripping away all the Typeclasses and abstract interfaces.
This is what we do.