:PROPERTIES:
:ID: b163be12-5892-4513-a7d1-9be469d5ae5d
:mtime: 20231018020758
:ctime: 20231018020744
:END:
#+title: algebraic data types
#+filetags: :public:project:
* Definition
An algebraic data type (ADT) is an initial algebra.
* Alternate Definition
An algebraic data type is a type built up with
sums, products, singletons, and recursion.
* Benefits of using ADTs
One benefit of using ADTs is that it can
[[id:fd1e50ac-0953-4358-af67-11b1d220d886][make illegal states unrepresentable]].
* Examples of Algebraic Data Types
** ADTs in [[id:8952459c-5076-4e68-8a68-5f658209f39e][OCAML]]
#+BEGIN_SRC ocaml
type vehicle = Bike | Motorbike | Car | Lorry
#+END_SRC
#+RESULTS:
: type vehicle = Bike | Motorbike | Car | Lorry
#+BEGIN_SRC ocaml
let wheels = function
| Bike -> 2
| Motorbike -> 2
| Car -> 4
| Lorry -> 18
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
wheels Lorry
#+END_SRC
#+RESULTS:
: 18
[[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] can also store data on ADTS
#+BEGIN_SRC ocaml
type vehicle = Bike
| Motorbike of int
| Car of bool
| Lorry of int
#+END_SRC
#+RESULTS:
: type vehicle = Bike | Motorbike of int | Car of bool | Lorry of int
All constructors of an ADT have the same type in OCAML
#+BEGIN_SRC ocaml
[Bike ; Motorbike 2 ; Lorry 5]
#+END_SRC
#+RESULTS:
| Bike | Motorbike | 2 | Lorry | 5 |
#+BEGIN_SRC ocaml
let wheels = function
| Bike -> 2
| Motorbike _ -> 2
| Car robin -> if robin then 3 else 4
| Lorry w -> w
#+END_SRC
#+RESULTS:
: <fun>
*** Recursive ADTs in OCAML
ADTs can be recursive in ocaml.
Here is an example of binary trees.
#+BEGIN_SRC ocaml
type 'a tree = Leaf
| Branch of 'a * 'a tree * 'a tree
#+END_SRC
#+RESULTS:
: type 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree
#+BEGIN_SRC ocaml
let my_tree = Branch(1 , Branch(2, Branch(4, Leaf, Leaf), Branch(5 , Leaf, Leaf)), Branch(3, Leaf, Leaf))
#+END_SRC
#+RESULTS:
: Branch (1, Branch (2, Branch (4, Leaf, Leaf), Branch (5, Leaf, Leaf)),
: Branch (3, Leaf, Leaf))
#+BEGIN_SRC ocaml
let rec count_branches = function
| Leaf -> 0
| Branch (_ , t1 , t2) -> 1 + count_branches t1 + count_branches t2
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml
let rec max_depth = function
| Leaf -> 0
| Branch (_ , t1 , t2) -> 1 + max (max_depth t1) (max_depth t2)
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
countLeaves my_tree
#+END_SRC
#+RESULTS:
: 5
#+BEGIN_SRC ocaml :exports both
max_depth my_tree
#+END_SRC
#+RESULTS:
: 3
#+BEGIN_SRC ocaml
let rec ftree k n = if n = 0 then Leaf else Branch (k,ftree (2 * k) (n - 1), ftree (2 * k + 1) (n - 1))
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
ftree 1 4
#+END_SRC
#+RESULTS:
: Branch (1,
: Branch (2, Branch (4, Branch (8, Leaf, Leaf), Branch (9, Leaf, Leaf)),
: Branch (5, Branch (10, Leaf, Leaf), Branch (11, Leaf, Leaf))),
: Branch (3, Branch (6, Branch (12, Leaf, Leaf), Branch (13, Leaf, Leaf)),
: Branch (7, Branch (14, Leaf, Leaf), Branch (15, Leaf, Leaf))))
*** Polymorphic ADTs in Ocaml
Ocaml ADTs can be polymorphic if they include 'a.
#+BEGIN_SRC ocaml
type 'a optional =
| Nothing
| Something of 'a
#+END_SRC
#+RESULTS:
: type 'a optional = Nothing | Something of 'a