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.

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
user40989
  • 2,860
  • 18
  • 35
  • 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 09 '13 at 10:40

2 Answers2

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.

justkris
  • 276
  • 1
  • 4
  • Do you think I should delete my answer? – Simon Bergot Dec 09 '13 at 12:45
  • No, it's fine with your warning of not hitting the exact vocabulary : ) – justkris Dec 09 '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 09 '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 09 '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 – daniel gratzer Dec 09 '13 at 17:28
  • So just to clarify: is the erasing of types an implementation detail? (i.e. is it possible to implement Haskell without erasing types?) –  Dec 09 '13 at 19:00
  • Well. Yes. Being slightly anal about it, if it's possible to run haskell programs without inspecting the types, I can surely run type-ful haskell code and ignore the types? – justkris Dec 09 '13 at 20:12
  • @Kris You can't inspect types in Haskell really, it's all done through typeclasses with are resolved statically, not the true dynamic reflection you can do in Python or Java – daniel gratzer Dec 09 '13 at 20:30
  • @jozefg Mind you, I meant the run-time system does not need to inspect the types on run-time, even if they are present in a (possibly) hypothetical implementation. True Haskell does not have true reflection, but must resort to things like Typeable. – justkris Dec 10 '13 at 22:19
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.

Simon Bergot
  • 7,930
  • 3
  • 35
  • 54
  • 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 09 '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 00:35