Assignment
2 Weight 1
Due Week 24 -- week beginning 16 April 2007
Demonstrate
in lab, hand-in by 9:00 following morning (Mon. for Friday lab)
FP2 -- Using Binary Search Trees
The aim of this
practical is to give you practice developing Haskell functions that extract
words from a string, store and manipulate information in a binary search tree,
and order lists.
Specifically, you
will develop functions that extract words and their frequencies, from an input
String, then store the words and their frequencies in a binary
search tree, extract words from the binary search tree to produce a list of
strings, ordered first by their frequency and then alphabetically.
For example, given
the text “The cat was on the Mat that was on the mat”,
you will build a binary search tree consisting
of words and frequencies,
(the,3)
/ \
(cat,1) (was,2)
\
(on,2)
/ \
(mat,2) (that,1)
and then output the list: “the, mat, on, was, cat, that”. Note that words with the same frequency are
ordered alphabetically (e.g. “mat” and “on” have same frequence,
so “mat” is listed before “on”).
Develop your program
in three stages.
Acceptance test:
Your function frequencyorder will be subject
to an acceptance test by your tutor during hand-in week. 8 out of 10 marks will be given to the acceptance test. Marks will also be awarded for clear
comments, layout and style. Hand in:
a copy of your documented program, and a brief status report.