Assignment 2 Weight 10 Distributed Week 20 Due Week 24 (week beginning April 18)

FP2 2005 -- Strings containing multiple words

The aim of this practical is to develop the Haskell function multiples that reports, for a given String, the number of multiple words in that String , and the maximum number of occurrences of a multiple word. The function is case insensitive.

For example, multiples has the following behaviour

multiples “the cat on the mat on the cat mat on”

=> “There are 4 multiples with a maximum number of 3 occurrences.”

multiples “case CASE case CAse xx”

=> “There is 1 multiple with 4 occurrences.”

multiples “The cat on”

=> “There are no multiples.”

You must binary search trees in your solution and you should develop your program in three stages.

1. Build binary search tree

Develop a function that takes a List of Strings, and produces a binary search tree containing Strings and Ints (a String and numbers of occurrences of the String ). Remember, case is irrelevant.

2. Evaluate binary search tree

Develop a function which takes a binary search tree and produces information about the number of multiple words and the maximum number of occurrences of the multiple words, i.e. the largest number of times any word is repeated.

3. Input and output

Do this last, when you are confident of your programming skills. The exercise requires you to convert the input, a String, into a list of words. You may assume that there is no punctuation in the String, that is, words are only separated by spaces. The output should be a String, in the format shown in the example.

Acceptance test: Your tutor will ask you to run a number of examples during the lab, 7 out of the 10 marks will be given to the acceptance test. Marks will also be awarded for clear comments, layout, tests and description of assumptions.

Hand in: a copy of your documented program, and a brief status report, by 9:00 on the morning after your lab, or 17:00 on the Friday if you are in a Friday lab.