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