provide a small
amount of test data for each question, and show results taken from the HUGS system (these can be
copied and pasted into the document.) Include the test data and output with each question, but
comment it out so that the .hs file that you hand in can be run. Block comments can inserted
between {- and -}.
1. Define a recursive function insert :: Int -> [Int] -> [Int] that inserts an
integer into the correct position in a sorted list of integers.
For example, insert 3 [1,2,4,5] should give the result [1,2,3,4,5].
2. Using insert, define a recursive function isort :: [Int] -> [Int] that sorts a
list of integers into the correct order.
3. Using a list comprehension, define a function
duplicated :: Eq a => a -> [a] -> Bool
that takes a list element and a list and returns True iff there is more than one copy of the
list element in the list. For example:
duplicated 10 [1,2,11,11] returns False,
duplicated 10 [1,2,10,11] returns False,
duplicated 10 [1,2,10,10] returns True.
4. Using another list comprehension, and the duplicated function, define a function
nodups :: Eq a => [a] -> Bool
that takes a list and returns True iff there are no duplicated elements in the list.
For example:
nodups [1,2,3,4,5] returns True
nodups [1,2,2,3,4,4] returns False
5. A simple method for encoding a string is to replace each character in the string by another
character given by a lookup table. Suppose that such tables are represented by the following
type:
type Table = [(Char, Char)]
For example, the table [(’a’,’b’),(’c’,’e’),(’r’,’q’)] replaces ‘a’ with ‘b’,
‘c’ with ‘e’ and ‘r’ with ‘q’.
A lookup table is valid if it gives a unique replacement for each character. That is, no two
distinct characters can be replaced with the same character and no character can have more
than one replacement.
Define a function valid :: Table -> Bool that decides if a table is valid, in the
sense that it contains no duplicates in its list of first components and no duplicates in its list
of second components.
Hint: Consider the function firsts, defined on page 39 of the Hutton text.
6. Define a function lookup :: Char -> Table -> Char that returns the