14 Dec

# Advanced IO

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)
```

## 1 Add

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
buildTree = foldr add Leaf
```

## 3 Search

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)
```