-- Algebraic data types
-- Given a set A of size a, and a set B of size b:
-- - How many elements are there in the union of A and B,
-- assuming they have no elements in common? a + b.
-- - How many distinct pairs of elements are there
-- where the first element is from A and the second is from B?
-- This kind of justifies thinking of union as "plus" and Cartesian
-- product (pairing) as "times".
-- Think of a type as a set of values.
-- If A and B are types, then A + B is the type of things which
-- are either a value of type A or a value of type B (together with
-- a tag telling you which it is). ("tagged union", "disjoint union").
-- If A and B are types, then A * B is the type of pairs
-- of values, where the first value has type A and the second has type
-- B.
-- Where do we see these in Haskell?
-- Product types:
p :: (Int, Bool) -- This is the "product type" Int * Bool
p = (3, True)
-- but also:
data IntBoolPair where
P :: Int -> Bool -> IntBoolPair
-- a single constructor with two things inside is a like a pair.
p2 :: IntBoolPair
p2 = P 3 True
-- Sum types:
data IntOrBool where -- This is the sum type Int + Bool
I :: Int -> IntOrBool
B :: Bool -> IntOrBool
-- having two constructors is like an "or".
-- Any language with objects has product types: an object gives us a
-- way to store multiple values together in one value, just like (3,
-- True) is a single value that contains multiple values.
-- But most OO languages (Python, Java, ...) do NOT have sum types.
-- Rust has sum types.
-- Some languages have very simple sum types in the form of enumerations.
-- Claim: sum types are a killer feature for languages like Haskell, Rust.
-- this is fine
data IntOrInt where
X :: Int -> IntOrInt
Y :: Int -> IntOrInt