Are types erased in Haskell?

Question

Haskell has a notion of “generic functions” that has some apparent similarity with common lisp—having neither experience with Haskell nor with common lisp, I might be very approximative here. This means that one can define a generic to_string facility to define a string representation for all types. Of course, the facility has to be defined in the special cases but there is a to_string function whose signature is α → string.

Are types erased in Haskell, as they are in OCaml? If yes, how does the implementation of “generic functions” in Haskell differ from that of common lisp, where types are dynamic, and thus not erased?

I understand that implementation details are compiler specific, but there is probably provisions common to many or all implementations.

Answer 1

The answer so far is misleading.

There needs to be made a distinction between "parametric" and "ad-hoc overloading" polymorphism. Parametric means "behaves uniformly for all types a", whereas "ad-hoc" -- what Simon refers to as polymorphic -- changes implementation based on the type.

Examples of both are reverse :: [a] -> [a], which is parametric, and show :: Show a => a -> String which is "ad-hoc" overloaded.

If you want more of an abstract intuition, I think it helps to consider the classes of natural language verbs that 'work' for all objects, like "to own" or "to think of" which pose no constraints on the object, but "to open" requires what we are talking about can be opened. I can 'think of a door', and 'open a door', while it makes no sense to e.g. 'open a tree'. To take the example even further "to open" is "ad-hoc polymorphic" as "to open a window" and "to open a complaint-ticket with customer service" are two very different things. If this seems forced - forget it! It works for me.

Both are resolved at compile-time, however, and in fact "erased". Modulo various GHC extensions and Template Haskell, etc. Types are in fact erased at compile time and never inspected on run-time.

Parametrically polymorphic functions behave identically for all types, so only one piece of code needs to be generated, whereas the compiler decides at compile time which version of a "type-classed" function needs to be run at a particular program point. This is also why the restriction of one instance per type per type class and the corresponding "newtype" work-around exists.

The implementation is detailed in SPJs textbook and Wadler and Blotts paper on type-classes.

Answer 2

warning: my background in CS is not very strong, so I might not always use the correct vocabulary, and I might be wrong on some points. Anyway, here is my understanding:

I think you are confusing generics with polymorphism.

Generic types such as List<Foo> are used to describe types which take other types as parameter, and allow richer type checking.

A generic function in haskell might be count:: List a -> Int. It accepts lists of any type, and returns the number of elements. There is only one implementation.

Usually, when defining List, you cannot assume anything about T. You can only store it and give it back.

Your to_string function is a polymorphic function, which means it will behave differently under different circumstances. In haskell, this is done with typeclasses, which works like adjectives for types.

You have a Show typeclass, which defines a show :: a -> String function.

When a type Foo implements the Show typeclass, it must provide the definition of show. This type can then be used in functions requiring the Show qualifier (as in Show a => a -> whatever). Haskell cannot erase types, since those functions have to find the correct implementation of the show function.