COMP0020: Functional Programming Higher Order Functions
COMP0020 Functional Programming Lecture 12
Recursive Algebraic Types
(RATs !)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 1 / 12
COMP0020: Functional Programming Higher Order Functions
Contents
Motivation : why do we need recursive algebraic types ?
Type domains revisited : the list Example RATs and Polymorphic RATs :
Lists Trees
Functions that operate on sorted trees
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 12
COMP0020: Functional Programming Higher Order Functions
Motivation
Using algebraic types we can enumerate the legal values of a new type
But what if we want more values than we can enumerate ?
How could we ever define our own types that were as powerful as num or [char] Easy ! — use recursion
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 3 / 12
COMP0020: Functional Programming Higher Order Functions
Type Domains Revisited
The type [char] has many legal values : the empty list [] , the list with one char [‘A’], and so on. However, the definition of a list is both simple and finite :
A list of char may be either the empty list
Or a char together with a list of char
This is the basis of the definition of algebraic types that potentially contain infinitely many values
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 4 / 12
COMP0020: Functional Programming Higher Order Functions
Example RATs/PRATs
A simple recursive algebraic type :
mylistchar : := MyNil | MyCons char mylistchar
A polymorphic recursive algebraic type : mylist * : := Empty | Cons * (mylist *)
A function that operates on a polymorphic recursive algebraic type :
myhd :: (mylist ∗) − > ∗
myhd Empty = error ”head of empty mylist” myhd (Cons x xs) = x
main = myhd (Cons ′A′ (Cons ′B′ (Cons ′C′ Empty)))
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 5 / 12
COMP0020: Functional Programming Higher Order Functions
Example RATs/PRATs (2)
Example tree type :
bintree * : := Emptytree | Node * (bintree *) (bintree *)
rightmost : : bintree * -> *
rightmost Emptytree = error “rightmost of empty tree” rightmost (Node x lt Emptytree) = x
rightmost (Node x lt rt) = rightmost rt
x = (Node 3 (Node 4 Emptytree Emptytree) Emptytree) main = rightmost x
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 6 / 12
COMP0020: Functional Programming Higher Order Functions
Functions on sorted trees
Adding an element to a sorted tree of numbers :
inserttree :: bintree num − > num − > bintree num
inserttree inserttree
Emptytree x = Node x Emptytree Emptytree
(Node v lt rt) x = Node v (inserttree lt x) rt, if (x <= v)
= Node v lt (inserttree rt x), otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 7 / 12
COMP0020: Functional Programming Higher Order Functions
Functions on sorted trees (2)
Membership of a sorted tree of numbers :
membertree :: bintree num − > num − > bool membertree Emptytree x = False membertree (Node v lt rt) x = True, if (v = x)
= (membertree lt x), if (x <= v) = (membertree rt x), otherwise
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 12
COMP0020: Functional Programming Higher Order Functions
Function on an unsorted tree
Compare with membership of an unsorted tree of numbers : memberutree :: bintree num − > num − > bool
memberutree Emptytree x memberutree (Node v lt rt) x
= False
= True, if (v = x)
= (memberutree lt x) \/ (memberutree rt x), otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 9 / 12
COMP0020: Functional Programming Higher Order Functions
Functions on sorted trees (3)
Removing an element from a sorted tree of numbers :
subtree :: bintree num − > num − > bintree num
subtree Emptytree x subtree (Node v lt rt) x
= Emptytree
= rt, if (v = x) & (lt = Emptytree)
= Node v (subtree lt x) rt, if (x < v)
= Node v lt (subtree rt x), if (x > v)
= Node new (subtree lt new) rt, otherwise
where
new = rightmost lt
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 10 / 12
COMP0020: Functional Programming Higher Order Functions
Summary
Summary
Motivation : why do we need recursive algebraic types ?
Type domains revisited : the list Example RATs and Polymorphic RATs :
Lists Trees
Functions that operate on sorted trees
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 11 / 12
COMP0020: Functional Programming Higher Order Functions
Summary
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 12 / 12