39

I once asked a question on haskell beginners, whether to use data/newtype or a typeclass. In my particular case it turned out that no typeclass was required. Additionally Tom Ellis gave me a brilliant advice, what to do when in doubt:

The simplest way of answering this which is mostly correct is:

    use data

I know that typeclasses can make a few things a bit prettier, but not much AFIK. It also strikes me that typeclasses are mostly used for brain stem stuff, wheras in newer stuff, new typeclasses hardly ever get introduced and everything is done with data/newtype.

Now I wonder if there are cases where typeclasses are absolutely required and things could not be expressed with data/newtype?

Answering a similar question on StackOverflow Gabriel Gonzales said

Use type classes if:

    There is only one correct behavior per given type

    The type class has associated equations (i.e. "laws") that all instances must satisfy

Hmm ..

Or are typeclasses and data/newtype somewhat competing concepts which coexist for historical reasons?

6 Answers 6

47

I would argue that typeclasses are an essential part of Haskell.

They are the part of Haskell that makes it the easiest language I know of to refactor, and they are a great asset to your being able to reason about the correctness of code.

So, let's talk about dictionary passing.

Now, any sort of dictionary passing is a big improvement in the state of affairs in traditional object oriented languages. We know how to do OOP with vtables in C++. However, the vtable is 'part of the object' in OOP languages. Fusing the vtable with the object forces your code into a form where you have a rigid discipline about who can extend the core types with new features, its really only the original author of the class who has to incorporate all the things others want to bake into their type. This leads to "lava flow code" and all sorts of other design antipatterns, etc.

Languages like C# give you the ability to hack in extension methods to fake new stuff, and "traits" in languages like scala and multiple inheritance in other languages let you delegate some of the work as well, but they are partial solutions.

When you split the vtable from the objects they manipulate you get a heady rush of power. You can now pass them around wherever you want, but then of course you need to name them and talk about them. The ML discipline around modules / functors and the explicit dictionary passing style take this approach.

Typeclasses take a slightly different tack. We rely on the uniqueness of a typeclass instance for a given type and it is mainly that choice, which permits us to get away with such simple core data types.

Why?

Because we can move the use of the dictionaries to the use sites, and don't have to carry them around with the data types and we can rely upon the fact that when we do so nothing has changed about the behavior of the code.

Mechanical translation of the code to more complex manually passed dictionaries loses the uniqueness of such a dictionary at a given type. Passing the dictionaries in at different points in your program now leads to programs with greatly differing behavior. You may or may not have to remember the dictionaries your data type was constructed with, and woe betide you if you want to have conditional behavior based on what your arguments are.

For simple examples like Set you can get away with a manual dictionary translation. The price doesn't seem so high. You have to bake in the dictionary for, say, how you want to sort the Set when you make the object and then insert/lookup, would just preserve your choice. This might be a cost you can bear. When you union two Sets now, of course, its up in the air which ordering you get. Maybe you take the smaller and insert it into the larger, but then the ordering would change willy nilly, so instead you have to take say, the left and always insert it into the right, or document this haphazard behavior. You're now being forced into suboptimal performing solutions in the interest of 'flexibility'.

But Set is a trivial example. There you might bake an index into the type about which instance it was you are using, there is only one class involved. What happens when you want more complex behavior? One of the things we do with Haskell is work with monad transformers. Now you have lots of instances floating around -- and you don't have a good place to store them all, MonadReader, MonadWriter, MonadState, etc. may all apply.. conditionally, based on the underlying monad. what happens when you hoist and swap it out and now different things may or may not apply?

Carrying around an explicit dictionaries for this is a lot of work, there isn't a good place to store them and you are asking users to adopt a global program transformation to adopt this practice.

These are the things that typeclasses make effortless.

Do I believe you should use them for everything?

Not by a long shot.

But I can't agree with the other replies here that they are inessential to Haskell.

Haskell is the only language that supplies them and they are critical to at least my ability to think in this language, and are a huge part of why I consider Haskell home.

I do agree with a few things here, use typeclasses when there are laws and when the choice is unambiguous.

I'd challenge however, that if you don't have laws or if the choice isn't unambiguous, you may not know enough about how to model the problem domain, and should be seeking something for which you can fit it into the typeclass mold, possibly even into existing abstractions -- and when you finally find that solution, you'll find you can easily reuse it.

2
  • Are you saying that with dictionaries, a function like sort would be bound to a VALUE and not to the TYPE and therefore operations involving two values a->a->a (like union) must decide which function to bake into the result? This can only be done safely if the two functions are the same, in which case they are not specific to a VALUE but to the TYPE. Sep 17, 2014 at 16:44
  • 9
    sort is fine. Any one particular function call can typically work fine with explicit 'dictionary passing' style. It is when you separate production from consumption that you can't always get away with it. e.g. constructing a Set in one pass and then looking things up in it later, then inserting more, and looking things up, merging, etc. In that lifecycle now there are several places where you could choose different instances leading to very different semantics, some combinations of which are unsound, but none of which are ruled out. Sep 17, 2014 at 19:20
32

Typeclasses are, in most cases, inessential. Any typeclass code can be mechanically converted into dictionary-passing style. They mainly provide convenience, sometimes an essential amount of convenience (cf. kmett's answer).

Sometimes the single-instance property of typeclasses is used to enforce invariants. For example, you could not convert Data.Set into dictionary-passing style safely, because if you inserted twice with two different Ord dictionaries, you could break the data structure invariant. Of course you could still convert any working code to working code in dictionary-passing style, but you would not be able to outlaw as much broken code.

Laws are another important cultural aspect to typeclasses. The compiler does not enforce laws, but Haskell programmers expect typeclasses to come with laws that all the instances satisfy. This can be leveraged to provide stonger guarantees about some functions. This advantage comes only from the conventions of the community, and is not a formal property of a language.

8
  • 7
    I would add that without typeclasses, we wouldn't get nice syntactic sugars like OverloadedStrings, Num literals, Monad do-notation, and more. These aren't essential to working in Haskell, but they certainly make it a lot less tedious.
    – bheklilr
    Sep 15, 2014 at 19:51
  • 7
    The first proper functional programming project I wrote was for rapid prototyping of Z specifications in Orwell. Implementing the maths library in dictionary passing style was very annoying indeed, sometimes with more dictionaries than actual arguments. Switching to Gofer's type classes was a huge relief.
    – AndrewC
    Sep 15, 2014 at 20:31
  • 1
    I imagine dictionary passing style gets even more complex once you get into things like recursive instances and the like. In fact, it seems like that might shift some computation from compile time (with typeclasses) to runtime (with dictionaries), but I haven't thought enough about it to be sure. Sep 15, 2014 at 21:19
  • 3
    Another nicety that typeclasses give you is a bit of compile time optimization. With a single typeclass instance that is known at compile time, the dictionary lookups can be performed as an optimization. This might not seem like a big deal, but if you have something like 1 + 2 * x - 12 * x * x inside an inner loop, that's be 8 dictionary lookups per loop (includes literals). That adds up. While there are ways of handling this kind of optimization in general, it happens automatically with type classes.
    – bheklilr
    Sep 15, 2014 at 21:40
  • 2
    Note that laws are not a unique feature of type classes by the way. You can define a data type and specify in the documentation that whatever you put in it has to satisfy certain properties in the same way and to the same effect as you specify laws on a type class. Sep 16, 2014 at 5:10
5

To answer that part of the question:

"typeclasses and data/newtype somewhat competing concepts"

No. Typeclasses are an extension to the type system, that allows you to make constraints on polymorphic arguments. Like most things in programming, they are, of course, syntactic sugar [so they aren't essential in the sense that their use can't be replaced by anything else]. That doesn't mean they're superfluous. It just means you could express similar things using other language facilities, but you'd lose some clarity while you're at it. Dictionary passing can be used for mostly the same things, but it's ultimately less strict in the type system because it allows changing behavior at runtime (which is also an excellent example of where you'd use dictionary passing instead of type classes).

Data and newtype still mean exactly the same thing whether you have typeclasses or not: Introduce a new type, in the case of data as new kind of data structure, and in case of newtype as a typesafe variant of type.

3

To expand slightly on my comment I would suggest always starting by using data and dictionary passing. If the boilerplate and manual instance plumbing becomes too much to bear then consider introducing a typeclass. I suspect this approach generally leads to a cleaner design.

3

I just want to make a really mundane point about syntax.

People tend to underestimate the convenience afforded by type classes, probably because they have never tried Haskell without using any. This is a "the grass is greener on the other side of the fence" sort of phenomenon.

while :: Monad m -> m Bool -> m a -> m ()
while m p body = (>>=) m p $ \x ->
                 if x
                 then (>>) m body (while m p body)
                 else return m ()

average :: Floating a -> a -> a -> a -> a
average f a b c = (/) f ((+) (floatingToNum f) a ((+) (floatingToNum f) b c))
                        (fromInteger (floatingToNum f) 3)

This is the historical motivation for type classes and it remains valid today. If we didn't have type classes, we'd certainly need some kind of replacement for it to avoid writing monstrosities like these. (Maybe something like record puns or Agda's "open".)

1

I know that typeclasses can make a few things a bit prettier, but not much AFIK.

Bit prettier?? No! Way prettier! (as others have already noted)

However the answer to this really depends very much where this question comes from.

  • If Haskell is your tool of choice for serious software engineering, typeclasses are powerful and essential.
  • If you are a beginner using haskell to learn (functional) programming, the complexity and difficulty of typeclasses can outweigh the advantages – certainly at the beginning of your studies.

Here are a couple of examples comparing ghc with gofer (predecessor of hugs, predecessor of modern haskell):

gofer

? 1 ++ [2,3,4]
ERROR: Type error in application
*** expression     :: 1 ++ [2,3,4]
*** term           :: 1
*** type           :: Int
*** does not match :: [Int]

Now compare with ghc:

Prelude> 1 ++ [2,3,4]
:2:1:
    No instance for (Num [a0]) arising from the literal `1'
    Possible fix: add an instance declaration for (Num [a0])
    In the first argument of `(++)', namely `1'
    In the expression: 1 ++ [2, 3, 4]
    In an equation for `it': it = 1 ++ [2, 3, 4]

:2:7:
    No instance for (Num a0) arising from the literal `2'
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Num Double -- Defined in `GHC.Float'
      instance Num Float -- Defined in `GHC.Float'
      instance Integral a => Num (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      ...plus three others
    In the expression: 2
    In the second argument of `(++)', namely `[2, 3, 4]'
    In the expression: 1 ++ [2, 3, 4] 

This should suggest that error-message-wise, not only are typeclasses not prettier, they can be uglier!

One can go all the way (in gofer) and use the 'simple prelude' that uses no typeclasses at all. This makes it quite unrealistic for serious programming but real neat for wrapping your head round Hindley-Milner:

Standard Prelude

? :t (==)
(==) :: Eq a => a -> a -> Bool
? :t (+)
(+) :: Num a => a -> a -> a

Simple Prelude

? :t (==)
(==) :: a -> a -> Bool
? :t (+)
(+) :: Int -> Int -> Int
10
  • Incorrect example. Gofer uses typeclasses, including overloading numeric literals, it just gives more sensible error messages with them. In fact, Gofer implemented constructor classes before ghc. Hugs didn't predate Haskell - hugs is short for Haskell User's Gofer System. Orwell would be a better exampke of typeclass-free programming, but it doesn't prove your point because both hugs and gofer give good error messages despite having typeclasses with overloaded numeric literals.
    – AndrewC
    Oct 4, 2014 at 8:38
  • @AndrewC: Please see the header in gofer's 'simple.prelude' -- it clearly says -- Simplified prelude without typeclasses... Shows how to use gofer without overloaded show, <=, == etc
    – Rusi
    Oct 5, 2014 at 1:47
  • But you'll find that with the standard prelude the error message is still Type error in application..., not No instance for... because gofer & hugs correctly assume that most of the time you've made a simple error with your function, not that you forgot to make an instance of some typeclass but used its functions anyway. Your argument was that typeclasses made error messages more confusing, but you compared gofer, which has good error messages with ghc which has confusing ones. You were comparing compilers, not language features. If you compare gofer & gofer simple, it'll be a valid point.
    – AndrewC
    Oct 5, 2014 at 7:35
  • Thats my first example: With standard prelude (having typeclasses) gofer's error messages are more helpful than ghc's. Example 2: One can expunge typeclasses completely if one chooses. So given that you concede that gofer's error messages (can be) better than ghc's, I dont know what's your point.
    – Rusi
    Oct 5, 2014 at 13:40
  • @AndrewC: As for gofer using overloaded numeric literals: Heres chap 14.4.4 of the gofer docs: In Haskell, any integer constant k appearing in an expression is treated as if the programmer had actually written "fromInteger k" ... Gofer does not support any form of default mechanism and overloaded numeric constants can only be obtained by explicit use of the fromInteger function
    – Rusi
    Oct 5, 2014 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.