Discussion Session 10: 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
module Example where

data IList = Nil
           | Cons Int IList
           deriving (Eq, Show)

data Option a = None
            | Some a

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 -> Option IList
iremove xs 0 = Some xs
iremove (Cons x xs) n = iremove xs (n - 1)
iremove xs n = None

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

IntTree.hs