Lecture 8: Elementary Haskell I
-------------------------------

(- new hw: implementing mergesort, quicksort)

1. list comprehensions:

  -- perform some operation on all elements of a list
  [x+1 | x <- [1,4,7]]

  -- cartesian product 
  [(x,y) | x <- [1,4,7], y <- [2,5]]

  -- filter a list
  [x | x <- [1,4,7], even x]

  -- all together now!
  [(x+1,y) | x <- [1,4,7], y <- [2,5], even x, odd y]


2. gently approaching type classes...

write ins (from insert insertion sort) in Haskell

  ins x [] = [x]
  ins x (y:ys) = if x < y
                 then x:y:ys 
                 else y:(ins x ys)

look at the type...

  ins :: Ord a => a -> [a] -> [a]

What about the types of the following?

mem x [] = False
mem x (h:t) = x==h || mem x t
  
mem :: Eq a => a -> [a] -> Bool

ops x y = (x+y, x-y, x*y)
  
ops :: Num a => a -> a -> (a,a,a)

arrange (x, y)
  | x <= y    = (x, y)
  | otherwise = (y, x)
  
arrange :: Ord a => (a,a) -> (a,a)

...note you can almost guess which type classes exist (like Eq and Num)


3. type classes

class Show a where
  show :: a -> String

data Currency = USD Int -- number of pennies

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x == y = not (x /= y)
  x /= y = not (x == y)
  -- minimal complete implementation: == or /=

-- instantiate Currency to Eq
instance Eq Currency where
  (USD c) == (USD d) = (c == d)