Abstraction levels in functional programming

Update on December 29, 2018: I misinterpreted what was meant by the implementation inhabitants, so I scratched the sentence that talked about it. Thanks, Brian!

Teaching and learning functional programming can be challenging. Many people will already have some experience of programming, which is usually very different from FP concepts. Analogies to other languages can sometimes do more damage than good (you’ve probably heard that you have to “unlearn” stuff when you’re starting to learn FP). I am delighted to see more people learning functional programming and find the effort that goes into making it accessible to a wider audience encouraging. I think that Elm has a great role to play in it.

I’m a fan of the work Brian McKenna does with Haskell on that front (my personal favourite are his streams on building Sonic in Haskell). His recent post on Higher Kinded Parametricity made me think about abstraction and its role in teaching and learning FP. The argument concerns Functor type class and the following function (not to be confused with the void type that originated in Algol, C and found in many popular OOP languages):

void ::
  Functor f =>
  f a
  -> f ()

To anyone versed in Haskell, this is a very basic example as Functor is a fundamental building block that appears in many places. To those who are less familiar, this could pose many new challenges.

Upon opening hoogle, you might find the definition of Functor.

The Functor class is used for types that can be mapped over…

Alright, so Functor is a class, but once again, these classes are nothing like OOP classes. Assuming some familiarity with the concept of Maybe data type (in some languages called Optional), what would happen if we instead started from the bottom of the abstraction ladder and worked our way up?

Haddock tells us that, for example, void replaces the contents of a Maybe Int with unit (unit is denoted with () ). In a basic form, we can express this as:

void :: Maybe Int -> Maybe ()
void Nothing = Nothing
void (Just _) = Just ()

But for the purpose of this function, it’s irrelevant if the parameter was Maybe Int, Maybe Bool or Maybe a, so we introduce parametric polymorphism:

void :: Maybe a -> Maybe ()
void Nothing = Nothing
void (Just _) = Just ()

A type starting with a lower case letter is polymorphic, meaning we can put another type in its place. Indeed, if we replace a with Int we’ll get exactly what we had in the previous level.

Next, we could show that the kind of operation on Maybe type where we do something with its contents is very common, so we define:

fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing = Nothing
fmap f (Just a) = Just (f a)

The first parameter accepts a function that gets applied to the content of the second argument, if it has any content.

We can now use this to implement our void function:

void :: Maybe a -> Maybe ()
void = fmap $ const ()

In Elm, this is where we reach the ceiling of abstraction (note that in Elm, Haskell’s const is named always and $ is named <| ) :

void : Maybe a -> Maybe ()
void = Maybe.map <| always ()

Or for the List data type:

void : List a -> List ()
void = List.map <| always ()

You would have to implement this for each data type for which you’d want to use this function, which can be tedious. But, is this really more complicated than in Haskell? Our void implementation for Maybe still has only a single inhabitant and the same with List.

Does this stop Elm from being incredibly practical or could this be a viable alternative for the currently most prominent web library React? I have reasons to think it exceeds React on many fronts¹². Those who pick up Elm will feel encouraged by being able to build great things using pure FP.

Haskell can, of course, take the abstraction to another level thanks to the wonderful concept of type classes first introduced by the living legend Philip Wadler and Stephen Blott in 1988 as a way of taming ad-hoc polymorphism:

void :: Functor f => f a -> f ()
void x = () <$ x

And it can go much further with that. After all, type classes are built on category theory, the language of mathematics. But even mathematicians can struggle with abstraction. I recommend the work of Eugenia Cheng, who explains mathematics and category theory in the most accessible down to earth way³. The following quote comes from her How to bake PI: An Edible Exploration of the Mathematics of Mathematics.

A moment where advanced mathematicians sometimes reach their abstract limit is category theory. They react in much the same way that teenagers do when they need x’s and y’s - they say they don’t see the point, and resist any further abstraction.

As programmers we are lucky to have the context for learning about these concepts.

If type classes are an essential part of your toolbox, then you’ll possibly find using Elm restricting. However, as this can be a scary territory for newcomers, it’s important to be sympathetic, especially if you teach FP using Haskell. Regardless, it shouldn’t have to be an exclusive choice. If and when Elm developers get the need to pursue the abstraction further, they’ll most definitely circle back to Haskell, PureScript or anything else with a more advanced type system. But I’m hopeful Elm will evolve to implement type classes in future.

We all have different ways in which we learn most effectively. Did your previous experience affect your learning of functional programming? Wouldn’t it be more constructive if FP communities were more united over the common goal of teaching FP? Please share your thoughts.

1. Blazing Fast HTML↩

2. Small Assets without the headache↩

3. Books by Eugenia Cheng↩