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.

1. Build binary search tree  Develop a function which takes a String of input text, and produces a binary search tree of pairs of String and Int (the words in the input text and their frequencies).  Case is irrelevant and the key for the binary search tree is String.  You may assume that the input text consists only of characters, and each word is separated by at least one space.  There are no punctuation symbols.
2. Produce final sorted list  Develop a function which takes a binary search tree of pairs of String and Int and produces a list of String.  The list of strings is ordered by their respective frequencies, and when the frequencies are the same, then the strings are ordered alphabetically.  Display the list of strings in the format given above in the example, i.e. separate each string by a comma, and put a full stop at the end.
3. Final program   Combine these functions into the function frequencyorder which takes an input String of text and produces the sorted list on the screen in the appropriate format. Use the function putStr, which takes a String as argument and displays it on the screen.

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.