Does Haskell Support Subtyping? It Depends.

March 28th, 2009

We’ve already seen that type-classes enable a very rich form of ad-hoc overloading (especially for basic arithmetic, where other languages require awkward workarounds).  If that were all that we could do with type-classes, it would more than justify their existence in a language.  However, that’s not all that we can do with type-classes — they’re good for much more.

A Few Extensions

I should start off by mentioning that the features of type-classes we’ll cover here are not part of the Haskell98 standard, but they’re regularly used and supported by GHC.  Provided that you’re using GHC, the code that follows in this article will work if you place the following line at the head of its file:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances #-}

Subtyping

In F# as well as Haskell, tuples are an important and commonly-used tool.  They are used to define composite types, joining an arbitrary (but finite, statically known) number of types together.  As we saw in the last article, they’re a convenient form for representing vectors.  However, in Haskell (and in F# for that matter) you may notice an odd thing about the standard functions provided for tuples: fst and snd.

Prelude> :t fst
fst :: (a,b) -> a
Prelude> :t snd
snd :: (a,b) -> b

These functions, fst and snd, are used to extract the first and second components of a 2-tuple (respectively).  Unfortunately, if we happen to be using 3-tuples, or 4-tuples (or n-tuples, for n > 2) we’re out of luck.  In those cases, we can’t even extract the first and second members without having to create something like:

fst3 (x,_,_) = x
fst4 (x,_,_,_) = x
… etc …

This is pretty silly.  This is clearly a case where some overloading would benefit us, so that we wouldn’t need to define the “fst” function with a different name for each possible size of tuple.  What we really want is something with a type signature like:

first :: Pair p a b => p -> a

Here we’re seeing a type-class constraint unlike the comparatively simple ones in the last article.  In essence, what “Pair p a b” must mean here, is that for some pair type “p” a type “a” and a type “b” can be extracted.  In the case of the “first” function we’ll just extract the “a” type, so the type of the “second” function must be:

second :: Pair p a b => p -> b

This scheme might sound reasonable, but how is the Haskell compiler supposed to know that the “p” type really does derive the “a” and “b” types?  For that, we need functional dependencies.  We can simply declare this dependency when we make the “Pair” type-class and Haskell’s type-checker will respect the restriction across all members of the type-class:

class Pair p a b | p -> a, p -> b where
   first  :: p -> a
   second :: p -> b

When filling out instances, we won’t have to mention these dependencies again.  So for example, if we wanted to define “first” and “second” over 2, 3, and 4-tuples:

instance Pair (a, b) a b where
   first  (x, y) = x
   second (x, y) = y

instance Pair (a, b, c) a b where
   first  (x, y, z) = x
   second (x, y, z) = y

instance Pair (a, b, c, d) a b where
   first  (x, y, z, w) = x
   second (x, y, z, w) = y

Now it’s true that we’re still filling out each and every definition, like we had done with fst3, fst4, etc.  However, we have at least gotten far enough to avoid having to know the size of the tuple when we’re using it!  It would be a strong language indeed that didn’t require this boilerplate, but it’s easy enough to generate it and forget it.

Of course we don’t have to stop at “first” and “second” (but we do have to stop somewhere).  We might also want to define “third” on any tuple as big or bigger than a triple.  Of course, a triple should already be a pair (i.e.: if third is defined on a tuple, first and second had better also be).  We can express this requirement with a type-class constraint, as well as the functional dependency required to claim that the triple’s type can produce yet another type (but we don’t need to re-declare the functional dependencies inherited from the Pair type):

class Pair p a b => Triple p a b c | p -> c where
   third :: p -> c

After that, it’s just as easy (if not a little tedious) to put more tuples into this type-class as well:

instance Triple (a, b, c) a b c where
   third (x, y, z) = z

instance Triple (a, b, c, d) a b c where
   third (x, y, z, w) = z

Points and Colored Points

It requires a bit of initial work (whether manual or automatic) to set this up, but once our generic tuple functions are in place we can then use them to achieve structural subtyping without any other work from the language.

For example, we may make a distinction between points and colored points:

data Color = Red | Green | White | Yellow | Blue

makePoint x y = (x, y)
makeCPoint x y c = (x, y, c)

However, either kind of point can have a distance (from the origin) defined:

distance :: (Pair p Float Float) => p -> Float
distance p = sqrt ((first p)**2 + (second p)**2)

To Be Continued

It’s fairly remarkable that type-classes (with these extensions) allow the recovery of subtyping in a language that otherwise wasn’t designed to support it.

In the next article we’ll continue investigating applications of multi-parameter type-classes with functional dependencies, to address a generic approach to incremental iteration and constant-time updates for arbitrary Haskell containers.

14 Responses to “Does Haskell Support Subtyping? It Depends.”

  1. augustss Says:

    You can get the tuple package from hackage for those tuple overloaded selectors (overloading, not subtyping).

  2. Jason Dusek Says:

    This is just interface definition/implementation and doesn’t really go as far saying, for example, (a,b,c) can be substituted for (a,b) in any circumstance whatsoever (whereas that is exactly what sub-typing allows).

    Not to say I am in favor of sub-typing; but this is not it.

  3. Purely-Functional Incremental Mutation » Lab49 Blog Says:

    [...] (An answer inside, plus the continuation of our exploration of type-classes.) [...]

  4. Kalani Thielen Says:

    Jason, Lennart,

    I assume (please correct me if I’m wrong) that you would define subtyping as the set of typing rules that e.g. make (a,b,c) a subtype of (a,b) (and therefore acceptable wherever (a,b) would be acceptable).

    However, with this set of type-classes in place, and if (for example) the tuple-destruction that’s built in to the language would use the overloaded first/second/third/etc functions, then I think that it would be indistinguishable from a system with explicit subtyping rules — ie: (a,b,c) *could* be substituted for (a,b) anywhere.

    I believe that Phil Wadler and Ben Pierce (in TaPL) have also commented at greater length on this relation between type-classes and subtyping.

    Maybe you could discuss in more detail where you see the differences. Thanks for commenting.

  5. Jason Dusek Says:

    @kalani :

    I’m not sure that it’s enough to use the typeclass for destructuring — you also need to hide the tuple types. Otherwise you could write a function of type `:: Tuple3 a b c -> t` and thus `Tuple2 a b` would not fit.

    I did not mean to suggest that typeclasses could not be used to implement sub-typing; however, this post is misleading in that it both misrepresents the amount of effort required and presents a phony definition of sub-typing.

  6. Kalani Thielen Says:

    Jason,

    On your first point, I’m not sure where you’re going — if a function expected a Tuple3 it shouldn’t accept a Tuple2 and I’d expect that should be rejected (whether in a language with “proper subtyping” or not).

    I hear what you’re saying about my “phony” and “misleading” definition — so could you please clarify for the benefit of the readers what a “proper” definition is? It seems pretty clear to me that there’s a deep similarity between type-classes and subtyping, especially at the level of typing rules.

    Also, when you say “this post is misleading in that it [...] misrepresents the amount of effort required” — required for what?

    Thanks for commenting.

  7. Jason Dusek Says:

    @kalani

    “On your first point, I’m not sure where you’re going — if a function expected a Tuple3 it shouldn’t accept a Tuple2 and I’d expect that should be rejected (whether in a language with “proper subtyping” or not).”

    That’s exactly what subtyping means — if `a` is a subtype of `b` then a `b` can be placed in any expression typed for an `a`. This is “Liskov substitutability” — “It should be possible to treat a specialized object as if it were a base class object.”. It’s what allows us to extend the range of object-oriented methods by introducing subtypes (subclasses) of the method’s declared type. See, for example “Type inference with simple subtypes” and it’s “coerce” rule.

    Subtyping allows us to confuse a concrete datatype with an interface. That is darkness.

    For record types in particular, subtyping — in the limited form called “structural subtyping” — is perennially attractive to Haskellers. GADTs allow us to implement a sort of subtyping.

  8. Jason Dusek Says:

    Oh, oops. I meant:

    If `b` is a subtype of `a` then a `b` can be placed in any expression typed for an `a`.

  9. Jason Dusek Says:

    Oh, rats. Please amend:

    “See, for example “Type inference with simple subtypes” and it’s “coerce” rule.”

    To:

    “See, for example “Type inference with simple subtypes” and its “coerce” rule.”

  10. Kalani Thielen Says:

    Jason,

    You wrote: “That’s exactly what subtyping means — if `a` is a subtype of `b` then a `b` can be placed in any expression typed for an `a`. [...]”

    Except that Tuple2 isn’t a subtype of Tuple3 (as you originally suggested) — it’s the other way around. As for the rest of what you said, it applies just as well to this system of type-classes. If you have a function that expects a Tuple2, you can pass in a Tuple3 (because a Tuple3 *is* a Tuple2).

    I’m still interested in your “proper” definition of subtyping, which excludes this system of type-classes. You originally made the claim that I gave a “phony” and “misleading” definition (which “misrepresents the amount of effort required”). But I don’t yet agree with that judgement — maybe you could make a clearer case.

    My formal understanding of subtyping comes from Ben Pierce’s “Types and Programming Languages,” and I’ve implemented type-inference programs for type-systems with his sub-typing rules and also for a type-system with type-classes. I’m not sure if you approach this subject from a similar background, but I think that if you compare the typing rules you’ll agree with me.

  11. Jason Dusek Says:

    “Except that Tuple2 isn’t a subtype of Tuple3 (as you originally suggested) — it’s the other way around.”

    Yes, that is correct — I apologize for my error.

    “As for the rest of what you said, it applies just as well to this system of type-classes. If you have a function that expects a Tuple2, you can pass in a Tuple3 (because a Tuple3 *is* a Tuple2).”

    Actually, given your example, it is “If you have a function that expects some `Pair p` you can pass a `Tuple3` because it conforms to `Pair`”. The `Tuple2` and `Tuple3` are concrete types and there is no way to form an “is a” relationship between concrete types in Haskell.

    If the only way to work with these types is through the typeclasses, it models subtyping as long as there is no way for users to see the concrete types `Tuple2` and `Tuple3`.

    “My formal understanding of subtyping comes from Ben Pierce’s “Types and Programming Languages,” and I’ve implemented type-inference programs for type-systems with his sub-typing rules and also for a type-system with type-classes. I’m not sure if you approach this subject from a similar background…”

    For someone so educated, you are surprisingly tongue-tied. It is lucky for you that ad hominem is a logical fallacy!

  12. Jason Dusek Says:

    I’m not learning anything from this conversation and I’ve said everything I might say in three different ways.

    Given my lack of background, it is best if I make no further remarks in this thread. Thank you for your time.

  13. Kalani Thielen Says:

    Jason,

    I think that you took the statement about TaPL in the wrong way. What I meant was that my understanding of the terminology of subtyping comes mostly from that book alone, and if you have some other background I’m curious to know what it is so that we can come to some consensus on this “proper definition” of subtyping.

    You’re right, I was using Tuple2 and Tuple3 as the type-classes representing those ideas — I thought that’s what we were talking about. At this point it looks like we’re at least in agreement that, provided that the primitive destructuring of a language works on these type-classes rather than explicit tuple types, you can use type-classes to achieve sub-typing.

    Thank you for commenting.

  14. Jason Dusek Says:

    “I think that you took the statement about TaPL in the wrong way.”

    Well in that case, please allow me to backpedal. I withdraw my earlier remarks.

    “I was using Tuple2 and Tuple3 as the type-classes representing those ideas…”

    Ah, okay — then we are in agreement, after all.