COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 15
Lists, Trees and Graphs
(link to implementation issues)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 7 / 27
COMP0020: Functional Programming
Example Programs
Contents
Representation in memory : LISTS Trees
I Representation in memory I Multiway branching trees
Graphs
I Source code
I Representation in memory
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 8 / 27
COMP0020: Functional Programming
Example Programs
How lists are represented in memory
We cover basic mechanisms : in practice, functional language implementations (such as Miranda) may use di erent representations in di erent contexts (e.g. whether the list is a data value embedded in the program and known at compile-time, or whether it is consructed dynamically at run-time).
A very simple strategy is to manage physical memory locations in groups of three (called “cells”) :
A “tag” (indicating the kind of cell) followed by two other items (“fields”)
Can be anywhere in memory
x = (‘A’ : (‘B’ : (‘C’ : []))) main = hd x
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 9 / 27
COMP0020: Functional Programming
Example Programs
Representing TREES in memory
exp ::= Const num
| App exp op exp
| Bracketed exp
op ::= Plus | Minus | Times | Divide
x :: exp
x = App (Const 6) Plus (Const 4) main = eval x
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 10 / 27
COMP0020: Functional Programming
Example Programs
Multiway branching trees
multitree * : := Empty | Node * [multitree *]
x : : multitree [char]
x = Node “hi” [ (Node “mum” []), (Node “x” []), Empty, (Node “bye” []) ]
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 11 / 27
COMP0020: Functional Programming
Example Programs
Multiway branching trees
multitree * : := Empty | Node * [multitree *]
x : : multitree [char]
x = Node “hi” [ (Node “mum” []), (Node “x” []), Empty, (Node “bye” []) ]
rightmost :: multitree ú ≠ > ú
rightmost Empty rightmost (Node x []) rightmost (Node x ns)
error “rightmost of empty tree”
=
= x
= rightmost (last ns1), if (ns1 ≥= [])
= x, otherwise
where
ns1 = filter (≥= Empty) ns
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 12 / 27
COMP0020: Functional Programming
Example Programs
Graphs : simple source code
multitree ú ::= Empty
| Node ú [multitree ú]
|| (as before)
graph :: graph= firstlink firstlink firstlink firstlink
multitree char a
Node ‘AÕ Node ‘BÕ Node ‘CÕ
a =
b =
c =
d= Node‘DÕ []
:: multitree ú
Empty
(Node x []) (Nodex(n:ns)) = n
[c, b ] [d ] [a, d ]
≠ > multitree ú
= error “firstlink of empty graphÕÕ
= error “firstlink of node with no first linkÕÕ
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 13 / 27
COMP0020: Functional Programming
Example Programs
Graphs : source code using a list
multitree ú ::= Empty
| Node ú [multitree ú]
|| (as before)
glist :: glist =
graph :: graph = firstlink firstlink firstlink firstlink
[multitree char ]
[ Node ‘AÕ Node ‘BÕ Node ‘CÕ Node ‘DÕ
[ (glist ! 2), (glist ! 1) ], [ (glist ! 3) ],
[ (glist ! 0), (glist ! 3) ], [] ]
multitree char hd glist
:: multitree ú
Empty
(Node x []) (Nodex(n:ns)) = n
≠ > multitree ú
= error “firstlink of empty graphÕÕ
= error “firstlink of node with no first linkÕÕ
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 14 / 27
COMP0020: Functional Programming
Example Programs
Graphs : representation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 15 / 27
COMP0020: Functional Programming
Example Programs
Graphs : representation after evaluating (firstlink graph)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 16 / 27
COMP0020: Functional Programming
Example Programs
Graphs : representation after evaluating all links
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 17 / 27
COMP0020: Functional Programming
Example Programs
Summary
Summary
Representation in memory : LISTS Trees
I Representation in memory I Multiway branching trees
Graphs
I Source code
I Representation in memory
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 18 / 27
COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 19 / 27