existentials.md

---

layout: post title: Object-Oriented Existentials

Object-Oriented Existentials

The title of the article should raise at least a few eyebrows. Existentials (or existential types) aren't really something you'd see in the same sentence as OO. They are parts of two separate worlds, the java-like corporate class hierarchies and the functional programming caves. As it turns out, they have a lot in common.

Introduction

For the uninitiated, let's look at what existentials actually are. This is going to involve some intermediate Haskell, but don't sweat it if you don't understand everything.

Problem / Rationale

Let's say we have some class:

class SomeClass a where
    someOp :: a -> Int

Let's add some instances just for fun:

instance SomeClass [Char] where
    someOp = length

instance SomeClass Int where
    someOp = id

Simple enough. Now, let's try to write a function in terms of that class:

combineTwo :: (SomeClass a, SomeClass b) => a -> b -> Int
combineTwo a b = someOp a + someOp b

Okay, okay. What about this one?

combineN :: (SomeClass a) => [a] -> Int
combineN = sum . map someOp

At first glance, it looks okay, but think about its signature for a while. Lists are homogenous in Haskell. That means we can't put objects of differing types into them. So while our combineN will work perfectly fine with a list of Ints or Strings, we won't be able to mix them together. Hence, we need a single datatype able to hold either.

Solution

First, we need some more power in the language, enabled with ExistentialQuantification extension. It enables us to quantify types, which practically means putting some freedom into them:

data SomeClassIsh = forall a. SomeClass a => SomeClassIsh a

To break it down and not take too much space:

1. The data type has no type parameters; it's a fully usable type.
2. forall a. introduces the variable on the right hand side, which is crucial
3. We use SomeClass constraint in data defition. This is bad in regular datatypes, but necessary here.

We need to "bridge" the instance as well:

instance SomeClass SomeClassIsh where
    someOp (SomeClassIsh a) = someOp a

As you can see, since there's no type parameter in the instance, we couldn't put the constraint there, and that's why it has to reside in the data definition.

And now, the improved combineN:

combineN :: [SomeClassIsh] -> Int
combineN = sum . map someOp

The only caveat is that in order to use it, every value has to be wrapped in the SomeClassIsh constructor; this is because we're storing actual data values of SomeClassIsh, not the types that are being wrapped.

So a use could look like that:

combineN [SomeClassIsh 5, SomeClassIsh "str"]