14 Dec

Read the examples for interact, lines, unlines, words, unwords, show and read from the exercises sheet.

The loudEcho function defined in Lab 7 can now be rewritten using interact. First we define a helper function, yell, which upper-cases everything we pass:

yell :: String -> String
yell = map toUpper

For example:

> yell "hello"
"HELLO"

> interact yell
abcABC  hiHI

Recap —  Binary Search Tree

Write a module BST which defines an abstract data type Tree a representing a Binary Search Tree containing objects of type a:

Then we define the data structure, a tree can either be empty (a Leaf) or have a left and right child (Trees as well):

data Tree a = Leaf
| Node a (Tree a) (Tree a)
deriving Show

The following tree: is represented like so:

test_tree :: Tree Int
test_tree = Node 7
(Node 3
(Node 1 Leaf Leaf)
(Node 5 Leaf Leaf))
(Node 10 Leaf Leaf)

Add a new element to the tree:

> add 1 (Node 5 Leaf Leaf)
Node 5 (Node 1 Leaf Leaf) Leaf
Solution
add :: Ord a => a -> Tree a -> Tree a
add x Leaf = Node x Leaf Leaf
add x (Node v left right) =
if x <= v
then Node v (add x left) right
else Node v left (add x right)

2 Build

Build a tree from the given list

> buildTree [1, 3, 5]
Node 5 (Node 3 (Node 1 Leaf Leaf) Leaf) Leaf
Solution
buildTree :: Ord a => [a] -> Tree a

Whether the given element is contained in the tree:

> search 3 test_tree
Just 3

> search 100 test_tree
Nothing
Solution
search :: Ord a => a -> Tree a -> Maybe a
search _ Leaf = Nothing
search x (Node v l r) | x == v    = Just v
| x < v     = search x l
| otherwise = search x r

4 Traversal

Inorder (left, root, right) traversal of the tree:

> inorder test_tree
[1, 3, 5, 7, 10]
Solution
inorder :: Tree a -> [a]
inorder Leaf = []
inorder (Node v left right) = inorder left ++ [v] ++ inorder right

5 Tree Map

Apply the given function to each element of the tree, similar to map for lists:

> inorder (treeMap (*2) test_tree)
[2, 6, 10, 14, 20]
Solution
treeMap :: (a -> b) -> Tree a -> Tree b
treeMap _ Leaf = Leaf
treeMap f (Node v l r) = Node (f v) (treeMap f l) (treeMap f r)

6 Next

For a given element x find the next one — the smallest one greater than x:

> next 4 test_tree
Just 5

> next 100 test_tree
Nothing
Solution
next :: Ord a => a -> Tree a -> Maybe a
next x t = if gtx == [] then Nothing else Just (minimum gtx)
where gtx = filter (>x) (traverse t)

7 Interaction

Write another module, Sorter, which uses the function from BST to sort a list of numbers. The list is entered from the keyboard, numbers delimited by whitespace:

Sorter> sortInput
1 5 2 3 6 9
[1, 2, 3, 5, 6, 9]

At the top of BST.hs, list what to export:

module BST (Tree,
buildTree,
inorder)
where

At the top of Sorter.hs, import them:

module Sorter where
import BST
Solution
sortInput :: IO [Int]
sortInput = do
line <- getLine
let split = words line
let numbers :: [Int]; numbers = map read split
let tree = fromList numbers
return (toList tree)