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,
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.