Algebraic data types

1. https://stanford-cs242.github.io/f19/lectures/03-2-algebraic-data-types.html
2. Look at Algebraic data types from this page: https://book.realworldhaskell.org/read/defining-types-streamlining-functions.html
3. https://jrsinclair.com/articles/2019/algebraic-data-types-what-i-wish-someone-had-explained-about-functional-programming/

An algebraic type system would include sum types, product types, and exponential types.

After we have most of our language fundamentals in place: variables, functions, numbers, and booleans, it is time to start building up data structures that give us rich representations of objects in the world.

That will start with algebraic data types, i.e. structs and enums.

The basic idea behind algebraic data types is to represent relations between data, specifically the notions of and and or. AND type is one that represents multiple types combined together, and an OR type represents a value that is exactly one of many possible types.

structs and tuples are both instances of the same core idea: types that contain multiple components. If the components are anonymous, we call them tuples1. And if the components have names, we call them records (or structs in the C case). Tuples are distinct from lists, as tuples have a fixed size. Records are distinct from dictionaries (aka maps, aka associative arrays) for the same reason.

Algebra of Algebraic data types

Product types and sum types are collectively called “algebraic” data types because they have algebraic properties similar to normal integers. It’s a neat little construction that might help you understand the relation between products/sums, although it probably won’t change much in the design of your programs.

Generally, you can understand the algebraic properties in terms of the number of values that inhabit a particular type. For example, the type bool is inhabited by two values, true and false. We write this as |bool|=2.