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 (`Tree`s 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)
``````