Lecture 9: Elementary Haskell III

0. guards...

- rewrite ins with guards (and an as-pattern)

  ins x [] = [x]
  ins x z@(y:ys)
    | x < y     = x : z
    | otherwise = y : (ins x ys)

  isort = foldr ins []


1. type classes

data Currency = USD Int

class Show a where
  show :: a -> String

-- instantiate Currency to Show, so (USD 101) looks like "$1.01"

class (Eq a) => Ord a where
  compare              :: a -> a -> Ordering
  (<), (<=), (>=), (>) :: a -> a -> Bool
  max, min             :: a -> a -> t
  min x y | x <= y    = x
          | otherwise = y
  max x y | x <= y    = y
          | otherwise = x
  -- minimal complete implementation is compare or <=

-- instantiate Currency to Ord

class (Eq a, Show a) => Num a where
  (+), (-), (*) :: a -> a -> a
  negate        :: a
  abs, signum   :: a -> a -> a
  fromInteger   :: Integer -> a

-- instantiate Currency to Num

2. infinite structures

- infinite list of perfect numbers

  perfects = [n | n <- [1..], perfect n]
    where perfect n = sum (properDivisors n) == n
          properDivisors n = [d | d <- [1..(n `div` 2)], divides d n]
          divides d n = n `div` d == 0

- infinite tree of all Integers

  data Tr = Tree Integer Tr Tr
    deriving (Show)

  everything = build 1
    where build n = Tree n (build (2*n)) (build (2*n+1))


---------------------------------------------------------------------
Programming challenge to the interested student: 
  breadth-first traversal of this tree