# Discussion Session 9: Play with Haskell¶

## Problem Set¶

• List Operation (Merge Sort)
• Tree Operation (Binary Search Tree)
• Conversion between List and Tree
• Higher Order Function
• Lazy Evaluation and Stream

## Code Example¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 module Quiz where data IList = Nil | Cons Int IList deriving (Eq, Show) ilength :: IList -> Int ilength xs = case xs of Nil -> 0 Cons x xs -> 1 + ilength xs itake :: IList -> Int -> IList itake xs 0 = Nil itake (Cons x xs) n = Cons x (itake xs (n - 1)) iremove :: IList -> Int -> IList iremove xs 0 = xs iremove (Cons x xs) n = iremove xs (n - 1) data Option a = None | Some a iremove_opt :: IList -> Int -> Option IList iremove_opt xs 0 = Some xs iremove_opt (Cons x xs) n = iremove_opt xs (n - 1) iremove_opt xs n = None -- Please implement the function to append two IList's. -- iappend :: IList -> IList -> IList -- Please implement the merge sort algorithm on IList -- merge_sort :: IList -> IList -- imap -- ifold data ITree = Leaf | Node Int ITree ITree deriving (Eq, Show) from_ilist :: IList -> ITree from_ilist Nil = Leaf from_ilist xs = let n = ilength xs in from_ilist_num xs n from_ilist_num :: IList -> Int -> ITree from_ilist_num xs 0 = Leaf from_ilist_num (Cons x xs) 1 = Node x Leaf Leaf from_ilist_num xs n = let n1 = n div 2 xs1 = itake xs n1 Some (Cons x xs2) = iremove_opt xs n1 t1 = from_ilist_num xs1 n1 t2 = from_ilist_num xs2 (n - 1 - n1) in Node x t1 t2 nats :: IList nats = genNat 0 genNat :: Int -> IList genNat n = Cons n (genNat (n + 1)) nat3 = itake nats 3 ifilter :: IList -> (Int -> Bool) -> IList ifilter Nil f = Nil ifilter (Cons x xs) f = if (f x) then Cons x (ifilter xs f) else ifilter xs f isEven x = if x mod 2 == 0 then True else False evens = ifilter nats isEven even3 = itake evens 3 genPrime0 (Cons x xs) f = if (f x) then genPrime0 xs f else let newf y = if (f y) then True else if (y mod x == 0) then True else False xs2 = genPrime0 xs newf in Cons x xs2 f0 n = if n < 2 then True else False genPrime xs = genPrime0 xs f0 primes = genPrime nats prime5 = itake primes 5 prime10 = itake primes 10 main :: IO () main = do putStrLn (show prime10) 

quiz.hs