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

1 Add

Add a new element to the tree:

> add 1 (Node 5 Leaf Leaf)
Node 5 (Node 1 Leaf Leaf) Leaf

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

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

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]

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]

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

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

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)