Programming Languages

@onlinepersona

An enum is a sum type because the number of inhabitants of the enum is the sum of the inhabitants of its parts.

A product type's number of inhabitants is the product of its parts' inhabitants. So a struct would fit that definition, or a pair, or a tuple.

Looking at the pic on your Cartesian product link:
if A is an enum {x,y,z} and B is an enum {1,2,3}, then a struct AxB has 9 possible inhabitants.

As you already figured out the types are sets with a certain number of elements.

Two types are isomorphic if you can write a function that converts all elements of the first one into the elements of the second one and a function which does the reverse. You can then use this as the equality.

The types with the same number of elements are isomorphic, i.e True | False = Left | Right. For example, you can write a function that converts True to Left, False to Right, and a function that does the reverse.

Therefore you essentially only need types 0, 1, 2, 3, ..., where type 0 has 0 elements, type 1 has 1 element, etc. and all others are isomorphic to one of these.

Let's use (*) for the product and (+) for the sum, and letters for generic types. Then you can essentially manipulate types as natural numbers (the same laws hold, associativity, commutativity, identity elements, distributivity).

For example:

2 = 1 + 1 can be interpreted as Bool = True | False

2 * 1 = 2 can be interpreted as (Bool, Unit) = Bool

2 * x = x + x can be interpreted as (Bool, x) = This of x | That of x

o(x) = x + 1 can be interpreted as Option x = Some of x | None

l(x) = o(x * l(x)) = x * l(x) + 1 can be interpreted as List x = Option (x, List x)

l(x) = x * l(x) + 1 = x * (x * l(x) + 1) + 1 = x * x * l(x) + x + 1 = x * x * (l(x) + 1) + x + 1 = x * x * l(x) + x * x + x + 1 so a list is either empty, has 1 element or 2 elements, ... (if you keep substituting)

For the expression problem, read this paper: doi:10.1007/BFb0019443

In most programming languages, integers are not considered a subset of floats, so when you have the type Int | Float, you can distinguish 3 from 3.0.

Well what is an enum except a chain of X | Y | Z | .... An enum can be any of its variants, and therefore the set of its possible values are just all possibilities of its variants added together.

Consider this enum:

enum Foo {
  A,
  B(bool),
}

The possible values for A are just one: A. The possible values for B are B( true ) and B( false ). So the total possible values for Foo are simply these sets combined: A or B( true ) or B( false ).

As for product types, what it is the product is, is still the same: the sets of possible values. Consider the possible values for the product of A and B. For every possible value of A, a value could be made by matching it with any possible value of B (so, multiplication). If there are 3 possible values of A, and two possible values of B, then the total number of possible combinations of these for the product type is 6.

In your example, Dog is a product of u8, another u8, and String. If you decide to add a Boolean field to this type, accordingly the size of the set of options would double, because for every possible Dog you currently have, two possibilities would be created, one with a true and one with a false.

As for your last question, some languages might use x as a product type syntax, but because tuples and structs are inherently product types, most languages use those as Syntax. For example in Haskell the product type of Dog and Cat would be written as (Dog, Cat).