PLClub Discussion Group

A Brief History of Algebraic Data Types

Sep 4 2020
Li-yao Xia

Abstract:

Algebraic data types are a staple of functional programming. In this talk, we will go back in time to the origins of algebraic data types. What is “algebraic” about algebraic data types? How did researchers of the time think about them? This adventure is an opportunity to shed some light into the evolution of functional programming and how it represents “a radical attack on the whole programming enterprise”1.

Optional homework:

  • Review the notion of algebraic data types (also called variants) in your favorite programming language (even if it is C++ 2). Two good places for catching up are OCaml’s manual3 and the Wikipedia article4.

  • Review the definition of an algebra5 (in the sense of “universal algebra”). To point out the relevant sections of the Wikipedia article: get the “Basic idea”, see how some of the “Examples” fit the definition, and also check out the definition of a homomorphism (in “Basic constructions”).

S. P. Jones, P. Wadler, in HOPL III, 2007.