What is Haskell's Data.Typeable?
HaskellTypeclassGeneric ProgrammingScrap Your-BoilerplateHaskell Problem Overview
I've come across references to Haskell's Data.Typeable, but it's not clear to me why I would want to use it in my code.
What problem does it solve, and how?
Haskell Solutions
Solution 1 - Haskell
Data.Typeable is an encoding of an well known approach (see e.g. Harper) to implementing delayed (dynamic) type checking in a statically typed language -- using a universal type.
Such a type wraps code for which type checking would not succeed until a later phase. Rather than reject the program as ill-typed, the compiler passes it on for runtime checking.
The style originated in Abadi et al., and developed for Haskell by Cheney and Hinze as a wrapper to represent all dynamic types, with the Typeable class appearing as part of the SYB work of SPJ and Lammel.
Reference
- Martín Abadi, Luca Cardelli, Benjamin Pierce and Gordon Plotkin, "Dynamic Typing in a Statically Typed Language", ACM Transactions on Programming Languages and Systems (TOPLAS), 1991.
- James Cheney and Ralf Hinze, "A lightweight implementation of generics and dynamics", Haskell '02: Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell, 2002.
- Lammel, Ralf and Jones, Simon Peyton, "Scrap your boilerplate: a practical design pattern for generic programming, TLDI '03: Proceedings of the 2003 ACM SIGPLAN International Workshop on Types in Languages Design and Implementation, 2003
- Harper, 2011, Practical Foundations for Programming Languages.
Even in the text books: dynamic types (with typeable representations) are statically typed languages with only one type, Harper ch 20:
> ### 20.4 Untyped Means Uni-Typed
> The untyped λ-calculus may be faithfully embedded in a typed language with recursive types. This means that every untyped λ-term has a representation as a typed expression in such a way that execution of the representation of a λ-term corresponds to execution of the term itself. This embedding is not a matter of writing an interpreter for the λ-calculus in ℒ{+×⇀µ} (which we could surely do), but rather a direct representation of untyped λ-terms as typed expressions in a language with recursive types.
> The key observation is that the untyped λ-calculus is really the uni-typed λ-calculus! It is not the absence of types that gives it its power, but rather that it has only one type, namely the recursive type
> D = µt.t → t.
Solution 2 - Haskell
It's a library that allows, among other things, naming types. If a type a is declared Typeable, then you can get its name using show $ typeOf x where x is any value of type a. It also features limited type-casting.
(This is somewhat similar to C++'s RTTI or dynamic languages' reflection.)
Solution 3 - Haskell
One of the earliest descriptions I could find of a Data.Typeable-like library for Haskell is by John Peterson from 1992: http://www.cs.yale.edu/publications/techreports/tr1022.pdf
The earliest "official" paper I know of introducing the actual Data.Typeable library is the first Scrap Your Boilerplate paper from 2003: http://research.microsoft.com/en-us/um/people/simonpj/Papers/hmap/index.htm
I'm sure there's lots of intervening history that someone here can chime in with!
Solution 4 - Haskell
The Data.Typeable class is used primarily for generic programming in the Scrap Your Boilerplate (SYB) style. See also Data.Data
The idea is that SYB defines a collection combinators for performing operations such as printing, counting, searching, substiting, etc in a uniform manner over a variety of user-created types. The Typeable typeclass provides the necessary plumbing.
In modern GHC, you can just say deriving Data.Typeable when defining your own type in order to provide it with the necessary instances.