13

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.

  • 5
    Remember you probably can't define a non-trivial function of type a -> String. You would more likely have a type constraint, like Show a => a -> String. – DJG Dec 9 '13 at 10:40
16

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.

  • Do you think I should delete my answer? – Simon Bergot Dec 9 '13 at 12:45
  • No, it's fine with your warning of not hitting the exact vocabulary : ) – Kris Dec 9 '13 at 12:48
  • Could you expand a little on why it is possible for GHC to erase types? Is it thanks to principal typing? – Simon Bergot Dec 9 '13 at 13:28
  • 2
    In general at runtime either the parametrically polymorphic functions may exist only once and call the ad-hoc polymorphic functions via some virtual dispatch method or all code may be generated for each type separately and calls statically linked. Either implementation is correct from the language point of view (note, that Haskell does not have polymorphic types; such thing can only be created with the GHC forall extension). – Jan Hudec Dec 9 '13 at 14:09
  • Are there any GHC extension which don't allow types to be erased? Overloading is static and without full dependent types I can't think of anything – jozefg Dec 9 '13 at 17:28
1

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.

  • In common lisp, polymorphic functions are called “generic functions” IIRC and I used the same (confusing) vocabulary. Your answer is useful and your final argument pretty convincing. .-) – user40989 Dec 9 '13 at 11:28
  • “There is only one implementation”—only one that makes sense, sure, but there are infinitely many possible. A function of type a → b has |b|^|a| possible implementations (consider the number of functions of type Bool → Bool), and lists have no upper size limit. – Jon Purdy Jun 14 '14 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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