Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why typeclasses instead of just pattern matching?

This is something of a philosophical question, but one I hope to have answered by official documentation or “word of god” (read: SPJ). Is there a specific reason that the Haskell committee chose to require explicit interfaces in the form of typeclasses rather than a more uniform solution based on pattern-matching?

As an example, take Eq:

class Eq a where
    (==), (/=) :: a -> a -> Bool
    x == y = not $ x /= y
    x /= y = not $ x == y

instance Eq Int where
    (==) = internalIntEq

Why could we not do something like this instead (bear with the pseudo-Haskell):

(==), (/=) :: a -> a -> Bool
default x == y = not $ x /= y             -- 1
default x /= y = not $ x == y

(Int a) == (Int b) = a `internalIntEq` b  -- 2

That is, if Haskell were to allow pattern-matching of ordinary data types, then:

  • Programmers could create ad-hoc classes, i.e., instance would be implicit (2)

  • Types could still be inferred and matched statically (SupportsEqualsEquals a => ...)

  • Default implementations would come “for free”

  • Classes could readily be extended without breaking anything

There would need to be a way to specify a default pattern (1) that, though declared before others, always matches last. Do any of these hypothetical features clash with something inherent in Haskell? Would it become difficult or impossible to correctly infer types? It seems like a powerful feature that’d gel very well with the rest of Haskell, so I figure there’s a good reason We Don’t Do It That Way™. Is this mechanism of ad-hoc polymorphism simply too ad-hoc?

like image 836
Jon Purdy Avatar asked Feb 02 '12 03:02

Jon Purdy


1 Answers

Is this mechanism of ad-hoc polymorphism simply too ad-hoc?

This question simply begs to be linked to Philip Wadler and Steve Blott's 1988 paper, How to make ad-hoc polymorphism less ad-hoc, where they present the idea of Type classes. Wadler is probably "word of God" on this one.

There are a few problems I see with the proposed "pattern match on any Haskell data type" technique.

The pattern matching technique is not sufficient to define polymorphic constants, such as mempty :: Monoid a => a.

The pattern matching technique still falls back onto type classes, except in a worse way. Type classes classify types (go figure). But the pattern matching technique makes it rather vague. How exactly are you supposed to specify that functions foo and bar are part of the "same" class? Typeclass constraints would become utterly unreadable if you have to add a new one for every single polymorphic function you use.

The pattern matching technique introduces new syntax into Haskell, complicating the language specification. The default keyword doesn't look so bad, but pattern matching "on types" is new and confusing.

Pattern matching "on ordinary data types" defeats pointfree style. Instead of (==) = intEq, we have (Int a) == (Int b) = intEq a b; this sort of artificial pattern match prevents eta-reduction.

Finally, it completely changes our understanding of type signatures. a -> a -> Foo is currently a guarantee that the inputs cannot be inspected. Nothing can be assumed about the a inputs, except that the two inputs are of the same type. [a] -> [a] again means the elements of the list cannot be inspected in any meaningful way, giving you Theorems for Free (another Wadler paper).

There may be ways to address these concerns, but my overall impression is that Type classes already solve this problem in an elegant way, and the suggested pattern matching technique adds no benefit, while causing several problems.

like image 119
Dan Burton Avatar answered Sep 28 '22 17:09

Dan Burton