Changeset 2409


Ignore:
Timestamp:
Oct 19, 2012, 4:48:06 PM (7 years ago)
Author:
mulligan
Message:

Some text about algebraic data types and their limitations. Needs to be finished.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Papers/polymorphic-variants-2012/polymorphic-variants.tex

    r2408 r2409  
    4040\label{sect.introduction}
    4141
     42%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     43% Section
     44%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    4245\section{Polymorphic variants}
     46\label{sect.polymorphic.variants}
     47
     48In this section we provide a self-contained \emph{pr\'ecis} of polymorphic variants.
     49For a more complete summary, we refer the reader to Garrigue's publications on the subject~\cite{dpm: todo}.
     50
     51Most mainstream functional programming languages, such as OCaml and Haskell, have mechanisms for inductively defining types through the use of \emph{algebraic data types}.
     52Each algebraic data type can be described as a sum-of-products, wherein we associate a fixed number of distinct \emph{constructors} to the type being introduced, all of whom expect a product of arguments.
     53Inductive data, modelled as an algebraic data type, is built incrementally from the ground-up using the constructors of that type.
     54Quotidian data structures---such as lists, trees, heaps, zippers, and so forth---can all be introduced using this now familiar mechanism.
     55
     56Having built data using constructors, to complete the picture we now need some facility for picking said data apart.
     57Functional languages employ \emph{pattern matching} for this task.
     58Given any inhabitant of an inductive type, by the aforementioned sum-of-products property, we know that it must consist of some constructor of that type applied to various arguments.
     59Using pattern matching we can therefore deconstruct algebraic data by performing a case analysis on the constructors of a given type.
     60
     61The combination of algebraic data types and pattern matching is powerful, and is arguably the main branching mechanism for most functional programming languages.
     62Further, using pattern matching it is easy to define new functions that consume algebraic data---the set of operations that can be defined for any given algebraic type is unbounded.
     63Unfortunately, when it comes to extending algebraic data types with new constructors these types are essentially `closed'.
     64We cannot simply extend an algebraic type with a new constructor.
     65We must introduce a new algebraic type with the additional constructor, lifting the old type---and any functions defined over it---into this type.
     66
     67Moving sideways, we can compare and contrast functional programming languages' use of algebraic data paired with pattern matching with the approach taken by object-oriented languages.
     68In mainstream object-oriented languages such as Java algebraic data types correspond to class hierarchies, each constructor corresponding to a subclass in this hierarchy.
     69Pattern matching is emulated using a dynamic dispatch mechanism.
     70Using the object-oriented approach it is easy to add a new `case' to a given hierarchy: just introduce a new subclass.
     71
     72[dpm: reword the above --- hard to phrase precisely ]
     73
     74
    4375\begin{itemize}
    4476 \item General introduction, motivations
Note: See TracChangeset for help on using the changeset viewer.