"algebraic data types"

Written By Atticus Kuhn
Tags: "public", "project"
: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

See Also

Foundations of Computer Science Notesmake illegal states unrepresentableOcamlOcaml

Leave your Feedback in the Comments Section