BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Dictionaries: lazy or strict type class witnesses? - Tom Schrijver
 s (K.U. Leuven)
DTSTART:20090515T141500Z
DTEND:20090515T144500Z
UID:TALK18224@talks.cam.ac.uk
CONTACT:Dominic Orchard
DESCRIPTION:Type classes are Haskell's acclaimed solution to ad-hoc overlo
 ading. This talk gives an introductory overview of type classes and their 
 runtime witnesses\, dictionaries. It asks the questions whether dictionari
 es should abide by Haskell's default lazy evaluation strategy.\n\nConceptu
 ally\, a type class is a type-level predicate: a type is an instance of a 
 type class iff it type provides an implementation for overloaded functions
 . For instance\, `Eq a' declares that type `a' implements a function `(==)
  :: a -> a -> Bool' for checking equality.\n\nType classes are used as con
 straints on type variables\, in so-called constrained polymorphic function
 s. E.g.  `sort :: Ord a => [a] -> [a]' sorts a list with any type of eleme
 nts `a' that are an instance of the Ord type class\, i.e. provide implemen
 tations for comparison.\n\nWitnesses for type class constraints are necess
 ary to select the appropriate implementation for the overloaded functions 
 at runtime. For instance\, if `sort' is called with Int elements\, the Int
  comparison must be used\, versus say Float comparison for Float elements.
 \n\nTwo forms of witnesses have been considered in the literature\, runtim
 e type representations and so-called dictionaries\, of which the latter ar
 e the most most commonly implementation\, e.g. in GHC. Haskell implementat
 ions treat dictionaries just like all other data\, as lazy values that may
  potentially consists of non-terminating computations. This way part of th
 e type checker's work\, who has made sure that the dictionaries do exist\,
  is simply forgotten. Is this really necessary? Can performance be gained 
 by exploiting the strict nature of dictionaries? 
LOCATION:GS15\, Computer Laboratory
END:VEVENT
END:VCALENDAR