Variants can be recursive and parameterized.
Let's write our own type for lists of integers.
type intlist =
| Nil
| Cons of int * intlist
type intlist = Nil | Cons of int * intlist
Here we have a recursive consructor. Our Cons constructor includes intlist.
We can write a length function.
let rec length = function
| Nil -> 0
| Cons (_, t) -> 1 + length t
val length : intlist -> int = <fun>
Now let's take the length of an int list!
Cons (1 , Cons (2, Nil));;
- : intlist = Cons (1, Cons (2, Nil))
Now we have an int list with the first element 1, and the second element 2.
length @@ Cons (1 , Cons (2, Nil));;
- : int = 2
Now what if the next day we decided we also wanted to implement string lists. One possibility would be to repeat all of this code, but the issue with that would be shadowing, so we'd need to change names. This won't scale well at all.
Whenever you're copying and pasting code, you pretty much doing something wrong. Rather than copying and pasting codes, good programmers extract ideas and parameterize this.
How do we do this? We use a parameterized variant:
type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
type 'a mylist = Nil | Cons of 'a * 'a mylist
Now we have a better version of our list! We have a variant type! We can use 'a in this definition wherever we want.
Now let's write a length function for mylist.
let rec length = function
| Nil -> 0
| Cons (_, t) -> 1 + length t
val length : 'a mylist -> int = <fun>
length (Cons (1, Nil));;
length (Cons (true, Nil));;
length (Cons (true, Cons (false, Nil)));;
- : int = 1
- : int = 1
- : int = 2
We could also make our syntax nicer!
type 'a mylist =
| []
| (::) of 'a * 'a mylist
let rec length = function
| [] -> 0
| _ :: t -> 1 + length t
type 'a mylist = [] | (::) of 'a * 'a mylist
val length : 'a mylist -> int = <fun>
let fib = 1 :: 1 :: 2 :: 3 :: 5 :: 8 :: 13 :: [];;
val fib : int mylist = (::) (1, (::) (1, (::) (2, (::) (3, (::) (5, (::) (8, (::) (13, [])))))))
Look at that! It has a type of int mylist
length fib;;
- : int = 7
And our length function works well too :)
In fact, this is exactly how the standard library implements lists:
type 'a list = [] | (::) of 'a * 'a list
That's it. list is a type constructor parameterized on the type variable 'a. [] and :: are just constructors of the variant.