Who said it cannot be typed? - Prof. Claudio Sacerdoti Coen
Channel: Functional Programming in Bologna
Date: 03/10/2018

Generalized Algebraic Data Types to the Rescue!

Terms (also called expressions) do all the computational work.

Types, if present at all, never get their hands dirty: they just stay still doing nothing, supervising if terms behave well. Many years ago some rebels wanted to put types to work too, by allowing computations in them as well. Dependent types were born, but types refused to cooperate and made the life of programmers so hard that only masochistic academics fell in love with them.

Fast forward a few decades: finally somebody understood how to reach a compromise between complexity and expressivity: Generalized Algebraic Data Types (GADTs) were born.

Currently, they are implemented (without run-time overhead over ADT!) both in OCaml and Haskell and there is on-going work to try to fit them in other languages as well (e.g. Scala).

By using GADTs one can

1) type expressions and functions that escaped all previous type systems (e.g. printf-like functions)

2) impose at compile time invariants on the data structures to prevent errors

3) achieve more precise typing for already typable functions, improving clarity and reducing the size of the code and the need for dealing in the code with impossible cases

4) make data types abstract (i.e. hiding their implementation) in restricted parts of the code, flexibly

5) write complex functions and types that nobody sane will be able to decipher...

Professor Claudio Sacerdoti Coen will try (and maybe fail..) to give a (very?) gentle introduction to the subject, assuming minimal knowledge on Algebraic Data Types and OCaml/Haskell.