Assignment 2 Trie

CSC324— Assignment 2

In this assignment, you will work in Haskell with a data structure given by a recursive data type, and you
will write interesting recursive functions over it. Note that you should also aim for reasonably efficient
algorithms and reasonably good and simple coding style, as usual.
Trie
A “trie” is a data structure that implements a dictionary (finite map) that uses strings for keys. The name
“trie” came from “retrieval”. Most confusingly (when you pronounce it), it is a tree structure indeed.
Here is an example (called albertTrie in the starter code): On the left is the dictionary represented, in the
middle is the trie picture, and on the right is how the provided printTrie function prints it.
key value
(empty string) 4
ace 9
pi 1
pit 9
top 5
ton 7
4
9
e
c
a
1
9
t
i
p
7
n
5
p
o
t
"" : 4
a
c
e : 9
p
i : 1
t : 9
t
o
n : 7
p : 5
In general, a trie node has a value or no value, and a collection of character-labelled edges/pointers
to child nodes. A trie works as a key-value dictionary by: It maps a string k to a value v iff starting from
the root node, traversing the path that matches the character sequence k is successful and reaches a node
that has the value v.
We use the standard library type Maybe a to represent the possible absence and presence of a value.
We use a list of (char, node) tuples to represent the collection of character-labelled [pointers to] children.
So a trie is coded as:
data Trie a = TrieNode (Maybe a) [(Char , Trie a)]
with a type parameter “a” so the user can choose the value type.
In this assignment, you will implement trie insertion and deletion in the file TrieInsertDelete.hs;
TrieDef.hs has the definitions and helpers, testTrieInsertDelete.hs has sample test cases.
Since the trie is immutable in functional programming, our insertion and deletion mean producing a
new trie rather than changing the original trie. Our insertion has replacement semantics: If the original
trie already maps k to some value, insertion produces a new trie that maps k to the new value.
Insertion Examples
Insertion example 1: trieInsert "top" 2 albertTrie. The old trie mapped “top” to 5; the new trie maps
“top” to 2.
1
key value
(empty string) 4
ace 9
pi 1
pit 9
top 2
ton 7
4
9
e
c
a
1
9
t
i
p
7
n
2
p
o
t
"" : 4
a
c
e : 9
p
i : 1
t : 9
t
o
n : 7
p : 2
Insertion example 2: trieInsert "tool" 0 albertTrie. Inserting a key like this can cause new child
nodes, even new paths, to appear.
key value
(empty string) 4
ace 9
pi 1
pit 9
tool 0
top 2
ton 7
4
9
e
c
a
1
9
t
i
p
7
n
0
l
o
2
p
o
t
"" : 4
a
c
e : 9
p
i : 1
t : 9
t
o
n : 7
o
l : 0
p : 5
Deletion Examples
Deletion example 1: trieDelete "pi" albertTrie. In this case, you lose a value, but you lose no nodes,
because the affected node still has descendents that hold values (in this example the child via the label
“t” still has a value).
2
key value
(empty string) 4
ace 9
pit 9
top 5
ton 7
4
9
e
c
a
9
t
i
p
5
p
7
n
o
t
"" : 4
a
c
e : 9
p
i
t : 9
t
o
n : 7
p : 5
Deletion example 2: trieDelete "ace" albertTrie. You are required to prune nodes and paths wherever a node has no value and has no descendents that hold values. Algorithmically, you can think and
implement this in the bottom-up direction: If a node has no value and no child, lose it; repeat at the
parent.
key value
(empty string) 4
pi 1
pit 9
top 5
ton 7
4
1
9
t
i
p
5
p
7
n
o
t
"" : 4
p
i : 1
t : 9
t
o
n : 7
p : 5
Deletion example 3: trieDelete "foo" albertTrie. In this case, since “foo” does not map to any value
in the original tree, the new tree is the same as the original tree. (A bit of cloning is OK if it makes your
code simpler.)
3