Sunday, December 30, 2012

On Existential Types

In Haskell, the type system is your best friend. It's incredibly flexible and general.

 90% of understanding Haskell is understanding the type system, understanding how it can help you, and where it falls short. In this post I'm going to talk about one of the Haskell language extensions designed to compensate for a shortcoming in the type system. Existential types.

Let's start of with a simple concept that's predominate throughout Lisp, heterogenous lists. In Scheme these lists are as natural as breathing, they're the syntax for goodness sakes. But in Haskell, the strong static typing system prevents you from creating anything beyond a homogenous list. Using the language extension ExistentialTypes we can come pretty darn close to creating a Scheme style list.

To enable Existential Types, (it's an extension so it must be explicitly turned on) we can use
> {-# LANGUAGE ExistentialQuantification #-}

How do we go about creating an Existential Type? It's pretty easy, here's one for you:
> data ET = forall a . CET a

Now this doesn't look too spectacular but notice something interesting, The type ET has no type variables. But, it has a polymorphic constructor, CET. This is the magic of Existential Types, they let us erase type variables from the left side of a data declaration, but still use them on the right.

For anyone from a Scala background, this should sound familiar. In fact most Java programmers have encountered existential types with the ? wildcard generics in Java. The forall a in Haskell is markedly similar to Java's MyClass<?>.  They have some odd and subtle differences though.

The forall syntax basically says, "Make this is polymorphic, but forget that it is". Now let's try to use ET, for example we could use a pattern to get at our hidden polymorphic variable

> access (CET a) = id

Well now comes the hiccup, we told Haskell that a could be any type. Well this is a problem because
we have no idea what operations our valid on the type! Furthermore, we can't do something like this:

> sumI :: [Int] -> Int
> sumI [] = 0
> sumI (i : is) = i + (sumI is)

Where we take a specific type of list, namely a list of Int's and do something that's specific to Int's, in this case, add them. This isn't an option for ET because ET is just a simple ADT, there's nothing polymorphic about it and so there's no way to specify what thing it holds.

 So so far we can do use id with ET... and that's not terribly helpful.

There is hope though, remember contexts? The =>? Well we can use them with our Existential Types to narrow down the field of types possible to place in ET from every single type to a specific subset, for example, showables.

> data RestrictedET = forall a . Show a => RET a

Now we can do something useful!

> showy :: [RestrictedET] -> String
> showy = concat . map (\(RET a) -> show a)

And now here's the cool part, it doesn't matter what types we give showy! We can wrap them with the RET constructor and as long as they implement Show they are all the same type! This means they can be stored together in a list! Here's an example of what I mean:

> showJunk :: String
> showJunk = showy [RET $ Just 1, RET 'm', RET False]

And that's compilable, wacky right? This is how Haskell let's us implement something similar to true heterogenous lists, we creat an existential type, and all we have to do is specify some constraint on the types possible, in the above example we said how everything had to be an instance of Show, and then we can wrap compatible values in our type sort of like a new type, and then we're all set!

If I just totally lost you, it may help to think of the Java version:

void showJunk(){
    List<Foo> ls = new ArrayList();
    ls.add(5); //Assume that Integer implements Foo
    ls.add(false); //Assume Boolean implements Foo
    for(Foo f : ls){;

A Larger Example

Let's do something cooler now... Let's create a poker game with various kinds of players and keep them in a list. It's possible to implement this sort of situation without Existential Types, but hey, what fun would that be. First we need class

> class Player a where
>     lose :: a -> String
>     win :: a -> String
>     bet :: a -> String
>    -- Actual functions to define gameplay

I'm too lazy to implement an actual game, but let's play with these simple functions. They allow players to have custom witty banter during each stage of the gameplay. For example, maybe we'll have a CockyPlayer data type which trash talks other players. In fact, let's do that
> data CockyPlayer = CockyPlayer
> instance Player CockyPlayer where
>     lose _ = "Um uhh... I meant to do that!"
>     win _ = "Hah! I told ya so!"
>     bet _ = "Y'all men or boys?"

Excusing my terrible banter (I'm a 16 year-old blogging about existential types, what'd you expect?) this is a pretty simple instance. Let's define a few more, just for kicks.

> data ShyPlayer = ShyPlayer
> instance Player ShyPlayer where
>     lose _ = "..."
>     win _ = "oh... yay..."
>     bet _ = "umm"
> data NormalPlayer = NormalPlayer
> instance Player NormalPlayer where
>     lose _ = "Darn!"
>     win _ = "Yeah!"
>     bet _ = "Here we go!"

Ok so we'll call that our table. Though I won't want to go to this casino, it'll be just fine for our purposes. Next let's define a existential type to wrap all our instances. In this case, we'll actually make it an instance to provide a more comfortable interface to work with. This also means that others could write code to operate on a Player instance and not have to know that it's in fact a existential type wrapping a Player instance. That tends to make them happier.

> data Wrapper = forall a . Player a => Wrap a
> instance Player Wrapper where
>     lose (Wrap a) = lose a
>     win (Wrap a) = win a
>     bet (Wrap a) = bet a

A little bit of boilerplate, but well worth it. On a sidenote, I feel like this should be possible to do with a mechanism similar to GeneralizedNewtypeDeriving's but in any case.

Let's implement a few more utilities: A really useful function to have would be wrap, which should be a variadic function which can wrap each type into a Wrapper instance. Creating a variadic function in Haskell though requires a little bit of hackery. Because of this I've decided to postpone it till the next blog post.

But now we can define functions like this
> type Response = [String]
> playHand :: [Wrapper] -> (Response, Response)
> playHand players = (betBanter, resultBanter)
>     where
>         betBanter     = map bet players
>         resultBanter = (win .head $ players) : (tail . map lose $ players)

And there you have it. We can call this function with something like this:
> play :: (Response, Response)
> play = playHand [Wrap CockyPlayer, Wrap ShyPlayer, Wrap NormalPlayer]

As you can see existential types are incredibly useful for creating generic functions and containers. If you liked this, I would check out GHC's RankNType extension, it has similar syntax but a very different concept that's worth looking into.

No comments:

Post a Comment