Existential type

From HaskellWiki
Revision as of 00:10, 9 October 2006 by DonStewart (talk | contribs) (category)

Jump to: navigation, search

Dynamic dispatch mechanism of OOP

Existential types in conjunction with type classes can be used to emulate the dynamic dispatch mechanism of object oriented programming languages. To illustrate this concept I show how a classic example from object oriented programming can be encoded in Haskell.

 class Shape_ a where
   perimeter :: a -> Double
   area      :: a -> Double
 
 data Shape = forall a. Shape_ a => Shape a
 
 type Radius = Double
 type Side   = Double
  
 data Circle    = Circle    Radius
 data Rectangle = Rectangle Side Side
 data Square    = Square    Side
 
 
 instance Shape_ Circle where
   perimeter (Circle r) = 2 * pi * r
   area      (Circle r) = pi * r * r
 
 instance Shape_ Rectangle where
   perimeter (Rectangle x y) = 2*(x + y)
   area      (Rectangle x y) = x * y
 
 instance Shape_ Square where
   perimeter (Square s) = 4*s
   area      (Square s) = s*s
 
 instance Shape_ Shape where
   perimeter (Shape shape) = perimeter shape
   area      (Shape shape) = area      shape
 
 
 --
 -- Smart constructor
 --
 
 circle :: Radius -> Shape
 circle r = Shape (Circle r)
 
 rectangle :: Side -> Side -> Shape
 rectangle x y = Shape (Rectangle x y)
 
 square :: Side -> Shape
 square s = Shape (Square s)
 
 shapes :: [Shape]
 shapes = [circle 2.4, rectangle 3.1 4.4, square 2.1]

(You may see other Smart constructors for other purposes).

Generalised algebraic datatype

The type of the parse function for this GADT is a good example to illustrate the concept of existential type.

Examples from the Essential Haskell Compiler project

See the documentation on EHC, each paper at the Version 4 part:

  • Chapter 8 (EH4) of Atze Dijksta's Essential Haskell PhD thesis (most recent version). A detailed explanation. It explains also that existential types can be expressed in Haskell, but their use is restricted to data declarations, and the notation (using keyword forall) may be confusing. In Essential Haskell, existential types can occur not only in data declarations, and a separate keyword exists is used for their notation.
  • Essential Haskell Compiler overview
  • Examples

Trac

Existential Quantification is a detailed material on the topic. It has link also to the smaller Existential Quantifier page.