My style of Haskell programming has been evolving over the 15 years that I have been working with it. It is turning into something that I would like to call “functor oriented programming”. The traditional use of typed functional programming focuses on data types. One defines data types to model the data structures that your program operates on, and one writes functions to transform between these structures. One of the primary goals in this traditional methodology is to create data structures that exclude erroneous states to the extent that is reasonably possible. As long as one ensures that pattern matching is complete, then the type system catches many errors that would otherwise lead to these erroneous states, which have been crafted to be unrepresentable.
Functor oriented programming is a refinement of this traditional focus on data types.
I was reminded of this concept recently when I was working with wren’s fantastic unification-fd library.
With functor oriented programming, one divides data structures into layers of functors that, when composed together, form the data structures that your program operates on.
Instead of writing transformations between data structures, one writes natural transformations between functors, where a natural transformation between functors F and G is a polymorphic function of type forall a. F a -> G a.
While traditional functions often operate on products of multiple inputs and/or outputs, with functor oriented programming one will often see functions operating on compositions of functors, including but not limited to distribution functions of type forall a. F (G a) -> G (F a) and half-way distribution functions forall a. F (G a) -> G (H a), and many others.
By dividing data structures up into layers of functors, one can create a separation of concerns that does not occur in traditional functional programming. With functor oriented programming, polymorphism is not necessarily about using functions polymorphically. Instead, polymorphism provides correctness guarantees by ensuring that a particular function can only touch the specific layers of functors in its type signature and is independent of the rest of the data structure. One benefits from polymorphism even when a function is only ever invoked at a single type.
The appearance of many natural transformations is one hallmark of functor oriented programming.
Higher-order natural transformations will invoke Rank2Types and RankNTypes, which is another hallmark of functor oriented programming.
Other hallmarks of functor oriented programming include open recursive types, which allows one to divide up recursive types into their layers of recursion and create natural transformations that operate on a single layer at a time.
Open recursive types plays an important role in wren’s unification library.
As fine of a language that Haskell is, it is not actually that suitable for functor oriented programming.
The problem is that, under normal circumstances, there is no reduction or equivalence classes at the type level.
For example, the identity functor does not transparently disappear during composition, the Compose functor is not transparently associative, and the Swap functor composed with itself does not reduce to the identity functor.
To cope with this one must litter one’s code with newtype wrapper and unwrappers to make all these natural transformations explicit.
In principle, these transformations should have no run-time consequences, but when they are used in higher-order ways, unfortunately they sometimes do.
Despite the problems, I am not aware of any another practical language that better supports this style of programming.
I think Haskell’s higher-kinded type classes and the progression of Monad, Applicative, Foldable, Traversable, etc. classes have been instrumental in leading to the development of this style of programming as they further motivate the division of one’s data structures into these layers of functors.
I have been thinking about writing this post for a few years now, and wanted to write something convincing; however, I do not think I am up to the task. Instead of trying to persuade the reader, I have elected to try to simply name and describe this style of programming so that the reader might notice it themselves when reading and writing code. Hopefully someone more capable than me can evangelize this approach, and perhaps even create a practical language suitable for this style of programming.