A Very Early History of Algebraic Data Types
13 hours ago
- #type-theory
- #history
- #programming-languages
- The article explores the early history of algebraic data types (AlgDTs), tracing their origins to John McCarthy's 1961 paper.
- McCarthy introduced concepts akin to sum and product types, though he didn't use those terms, focusing instead on 'direct union' and 'Cartesian product'.
- The naming of sum and product types likely comes from their cardinality properties, where sum types' cardinalities add and product types' multiply.
- Tony Hoare and Rod Burstall further developed these ideas, with Hoare emphasizing their use in error detection and Burstall applying them in functional programming.
- ML, developed by Robin Milner, was among the first languages to implement sum and product types, using '+' for sum types and 'x' for product types.
- HOPE introduced tagged unions and pattern matching, enhancing the usability of sum types in functional programming.
- The article concludes by noting the influence of these developments on modern programming languages, despite initial resistance in imperative programming circles.