Object Oriented Programming in Haskell

In object oriented programming an object is a value with a well-defined interface. The internal state of the object is closed to the outside world (encapsulation), but the behaviour of an object can be modified by redefining one or more of the functions in the object’s interface, typically through subclasses (inheritance). The internal state of the object is open to, and can be extended by, such subclasses. This is known as the open/closed principle.

For some problem domains this way of modelling is extremely suitable, and so one may wonder if we can take a similar approach in a purely functional language like Haskell, without losing purity. An obvious choice is to model an object as a record of functions that correspond to the public interface to that object. For example, we might define the “interface” of counters as

data Counter = Counter {
      tick    :: Counter
    , display :: Int
    }

and we can define a “constructor” for this class as

mkCounter :: Int -> Counter
mkCounter n = Counter {
      tick    = mkCounter (n + 1)
    , display = n
    }

The problem with this approach is that it does not allow us to “redefine methods” in any meaningful way. In particular, suppose we tried to define a “subclass”¹ of counters which doubles the count in the display method:

twice :: Int -> Counter
twice n = (mkCounter n) {
      display = n * 2
    }

If we tried this

display (tick (tick (tick (twice 0))))

we will get 3, not 6. In this blog post we will explain what open recursion is, provide some runnable examples that you can evaluate one step at a time to develop a better intuition for how it works, and show how it can be used to solve the problem above. These results are not new, but we hope that this blog post can serve to make them a bit more accessible to a larger audience.

We then discuss how we can extend this approach using lenses to allow “inheritance” to also extend the “state” of the object.

Explicit fixpoints

Most beginner Haskell students study the factorial function:

fac :: Int -> Int
fac 1 = 1
fac n = n * fac (n - 1)

Many find it confusing because the concept of recursion, or self-reference, is hard to grasp at first. To a seasoned Haskell programmer recursion comes completely naturally, but they too might have to stop and think to answer the following question: can we define fac in such a way that we can later extend it? For example, we’d like to be able to define a function skim that subtracts 1 (i.e. “skims from the top”) from the result of every recursive call; that is, skim should be equivalent to

skim :: Int -> Int
skim 1 = 1
skim n = n * skim (n - 1) - 1

but it should be defined in terms of fac. At the risk of stating the obvious, this is not a solution:

skim :: Int -> Int -- wrong
skim n = fac n - 1

since although it subtracts 1 from the final result of fac, it doesn’t do this at every recursive call.

The problem is that as defined fac cannot be extended; the recursive call to fac is fixed (“resolved”) at the definition point; it will always call itself, no matter how we wrap it. If we want to avoid this, we need to “delay” the resolution of that recursive call. Concretely, instead of calling itself, fac will take an additional parameter:

fac :: (Int -> Int) -> Int -> Int
fac r 1 = 1
fac r n = n * r (n - 1)

The intuition is that when we pass “itself” as that r parameter, we recover the original factorial function. We do that through the use of fix:

fix :: (a -> a) -> a
fix f = f (fix f)

To understand how this works, step through the evaluation² of the computation of 5 factorial

Prev Next (step Step, Status)

Term

Heap

Note that the function we call is fix fac, and that every time we expand that we end up with fac (fix fac); in other words, the recursion argument is the same as the function we call. This corresponds to our intuition above that we must pass the function “itself” as its recursion argument.

Open Recursion

So what is this useful for? Well, it is now possible to define skim in terms of fac:

skim :: (Int -> Int) -> Int -> Int
skim r 1 = 1
skim r n = (fac r n) - 1

Just like fac, skim also takes the function for the recursive call as an argument; this would for example make it possible to introduce further “extensions” later on. Only once we call fix do we “tie the knot”:

Prev Next (step Step, Status)

Term

Heap

Note that each time we expand fix skim, we end up with skim (fix skim); in other words, the recursive call that we pass to both skim and fac is fix skim. Delaying the resolution of the recursive call, leaving the recursion “open”, is the key ingredient that makes it possible to adjust the result of fac at every recursive call.

Inheritance

Let’s now go back to the example at the start of this blog post. Hopefully it should now be clear why the definition of twice as stated did not work: the recursion in mkCounter is resolved too early; when we construct a new object in tick, we want to construct a new “twice” object, not a new base object. We can use the exact same open recursion technique to make that happen. The definition of the “interface” itself remains unchanged

data Counter = Counter {
      tick    :: Counter
    , display :: Int
    }

but we add an additional “recursion argument” to mkCounter and twice:

mkCounter :: (Int -> Counter) -> (Int -> Counter)
mkCounter self n = Counter {
      tick    = self (n + 1)
    , display = n
    }

twice :: (Int -> Counter) -> (Int -> Counter)
twice self n = (mkCounter self n) {
      display = n * 2
    }

This works in precisely the same way that skim did, except that instead of subtracting 1 from the result of each recursive call, we now override display after each recursive call to mkCounter. Step through the evaluation of

display (tick (tick (tick (fix twice 0))))

to see this happening in detail:

Prev Next (step Step, Status)

Term

Heap

Note that, as before, fix twice evaluates to twice (fix twice), so that the recursion parameter that we pass to both mkCounter and twice will be fix twice; thus, although we do not redefine tick, it still constructs the right kind of object.

Recap: Lenses

Before we continue discussing how we can extend the state of the object, we will briefly recap lenses. If this is old hat to you, feel free to skip this section.

Lenses are a big topic in their own right, and there is no way we can do them justice in this blog post. We will recap the concepts we need for our purposes, but if you have never seen lenses before, this section may not be the most accessible introduction.

A Lens a b is essentially a way to “access” a small part (of type b) of a larger structure (of type a); we can both get that smaller part and we can modify it:

data Lens a b = Lens {
      get    :: a -> b
    , modify :: (b -> b) -> (a -> a)
    }

Lenses form a category; all that means is that we can always construct a lens from a structure to itself, and that we can compose lenses:

instance Category Lens where
  id     = Lens id id
  l . l' = Lens (get l . get l') (modify l' . modify l)

As an example, here are the lenses for the first and second component of a pair:

_1 :: Lens (a, b) a
_1 = Lens fst first

_2 :: Lens (a, b) b
_2 = Lens snd second

(where first and second come from Data.Bifunctor).

Extending state

When we inherit from a class in object oriented programming, in addition to redefining some functions we can also extend the state of the object: we can add more fields. Let’s see how we can do this in our approach to modelling objects. Let’s start with a minor extension of the Counter interface:

data Counter = Counter {
      tick    :: Counter
    , tock    :: Counter
    , display :: String
    }

In our “base” implementation, both tick and tock just increment the counter’s internal state:

mkCounter :: (Int -> Counter) -> (Int -> Counter)
mkCounter self n = Counter {
      tick    = self (n + 1)
    , tock    = self (n + 1)
    , display = show n
    }

But now suppose we want to “inherit” from this base implementation, and introduce a “new field” so that we can count the ticks and tocks separately. If we follow the same approach as above, we’ll find that we’ll soon get stuck:

ticktock :: ((Int, Int) -> Counter) -> (Int, Int) -> Counter
ticktock self (n, m) = mkCounter (self . _reconstruct) n

The ticktock counter needs two integers in its state, for the two separate counters. But which self do we pass to mkCounter? We can’t just pass ticktock’s own self argument directly, because the types don’t line up. In the definition above we have left open a hole _reconstruct :: Int -> (Int, Int). That is, we somehow have to reconstruct the “extended” state of the subclass from just the state of the superclass. Why is this necessary? Well, let’s trace the constructor calls for the first tick after the ticktock counter is constructed:

• We start with fix ticktock (0, 0)
• This unfolds to ticktock (fix ticktock) (0, 0)
• The ticktock constructor calls mkCounter (fix ticktock . reconstruct) 0.
• Notice what happens in tick now: tick calls self (n + 1), which expands to
  
  (fix ticktock . reconstruct) (n + 1)
  
  i.e. 
  
  fix ticktock (reconstruct (n + 1))
  
  This means that although tick is constructing a ticktock counter (rather than a base mkCounter), every time we call tick the state of the subclass is reconstructed from the state of the superclass.

Clearly, this is not going to work. Instead what we need to do is parameterize the constructors with the state of the object; something like

mkCounter :: (st -> Counter) -> (st -> Counter)

Of course, this signature as it stands can’t quite work, because now mkCounter doesn’t know anything about st. To make it work, we will pass a lens to mkCounter that gives it access to the state it needs:

mkCounter :: Lens st Int
          -> (st -> Counter) -> (st -> Counter)
mkCounter l self st = Counter {
      tick    = self (modify l (+ 1) st)
    , tock    = self (modify l (+ 1) st)
    , display = show (get l st)
    }

In object oriented programming, subclasses can only extend the state of the superclass; they cannot remove fields. This is also the intuition of the lens parameter: it tells the constructor of the “superclass”: the state may have been extended, but it will at least contain the state that you need.

With this generalization we can now define ticktock:

ticktock :: Lens st (Int, Int)
         -> (st -> Counter) -> (st -> Counter)
ticktock l self st = (mkCounter (_1 . l) self st) {
      tock    = self (modify (_2 . l) (+ 1) st)
    , display = show (get l st)
    }

Like mkCounter, ticktock gets a lens parameter (because its state may later be extended again). The self parameter that we pass to mkCounter is now just the unmodified self parameter that ticktock gets; the only difference is that the lens argument we pass to ticktock is the composition of the lens argument to ticktock with _1, essentially telling mkCounter that the first component of the pair or integers in ticktock is the state that mkCounter should use.

When we now evaluate

display (tick (tock (tick (fix (ticktock id) (0, 0)))))

we will get

(2, 1)

as expected.

Conclusions

It is important when writing code to choose the right way to model the problem domain. For some problem domains the most natural way to model it is object oriented programming. Of course, since we are Haskell programmers, we’d ideally like this to be referentially transparent object oriented programming, with no side effects.

Object oriented programming in Haskell has a long history, with encodings ranging from the very ambitious in Haskell’s Overlooked Object System by Oleg Kiselyov and Ralf Lämmel, to the very minimal in the use of OOP in the design of the Yi editor as described by JP Bernardy, and everything in between, such as Ruben de Gooijer’s masters thesis wxHaskell for the web or the recent blog post series on Object-Oriented Haskell by Tobias Dammers.

The use of open recursion to model inheritance is well-known; for instance, it is described in Chapter 18, Case Study: Imperative Objects in Pierce’s excellent book Types and Programming Languages. It is also a key component in Bruno Oliveira’s paper The Different Aspects of Monads and Mixins. Of course, the use of explicit fixpoints has myriad other uses also; for instance, explicit fixpoints at the type level is what makes designs such as Data types à la carte by Wouter Swierstra possible. Despite being well-known, it can nonetheless be confusing; our hope is that this blog post can help to make the technique more accessible.

The use of lenses as we presented it in this blog post to allow “subclasses” to extend the state is to the best of my knowledge novel, although Jonathan Brachthäuser’s master’s thesis on Modularization of Algorithms on Complex Data Structures in Scala comes close. In hindsight it seems a very natural solution to the problem. It also provides a very direct implementation of the open/closed principle, where subclasses have full access to the object’s internal state, but only the public API is visible to external clients.

Interestingly, it also generalizes subtyping in traditional object oriented languages. While encapsulation (state hiding) in OOP languages means that an object’s internal state can be changed without affecting clients of that object, it is not possible to change an object’s internal representation in subclasses. In our approach this is perfectly possible, as long as there is a lens from the state of the subclass to the state of the superclass; in general, this lens can be arbitrary complex (although efficiency should be considered, of course).

Footnotes

1. Actually, this is closer to modelling prototype based inheritance, like in JavaScript or Self, rather than class-based inheritance. We will ignore this difference in this blog post, since class-based inheritance is much better known.

2. Added a seq node just to make the evaluation a little easier to understand (no need to allocate a thunk).