Problems 2 – Sample Solutions

Algebraic Types and Type Inference

1. Assuming that the item is in the tree:

data BSTree a = Nil | Node a Int (BSTree a) (BSTree a) deriving Show

delete :: Ord a => a -> BSTree a -> BSTree a

delete x Nil = Nil

delete x (Node y s t1 t2)

| (x>y) = Node y (s-1) t1 (delete x t2)

| (x<y) = Node y (s-1) (delete x t1) t2

| isNil t1 = t2

| isNil t2 = t1

| otherwise = join t1 t2

where

join t1 t2 = Node minimum newsize t1 newtree

min :: Ord a => BSTree a -> a

min (Node x s Nil t2) = x

min (Node _ _ (Node y s t1 t2) _) = min (Node y s t1 t2)

minimum = min t2

newsize = (size t1) + (size t2)

size Nil = 0

size (Node y s t1 t2) = s

isNil Nil = True

isNil (Node _ _ _ _) = False

newtree = delete minimum t2

test1 = Node 6 5 (Node 3 3 (Node 1 1 Nil Nil) (Node 4 1 Nil Nil)) (Node 8 1 Nil Nil)

2

i. f1 :: Int -> Int

ii. f2 :: a -> b -> (a,b,a)

iii. f3 :: Int -> String -> (Int,String)

iv. f4 :: no type, unless rhs of first eqn is [a], then Int -> [Int] -> Int]

v. f5 :: a -> b -> [(b,a)] -> [(b,a)]

vi. f6 :: (d -> (b -> c)) -> d -> [b] -> [c]