purely functional data structure 2章の問題の一部

pfds.2.hs

data Tree a = E
              | T (Tree a) a (Tree a)
              deriving (Show)

empty :: Tree a -> Bool
empty E = True
empty (T _ _ _) = False

insert :: Ord a => a -> Tree a -> Tree a
insert x E = (T E x E)
insert x (T a y b) | x < y = (T (insert x a) y b)
                   | x > y = (T a y (insert x b))
                   | otherwise = (T E x E)

member :: Ord a => a -> Tree a -> Bool
member _ E = False
member x (T a y b) | x < y  = member x a
                   | x > y  = member x b
                   | otherwise = True

-- ex2.2
member2 :: Ord a => a -> Tree a -> Bool
member2 x t = loop t (\last -> False)
  where 
    loop E f = f x
    loop (T a y b) f | x >= y = loop b (\last -> last == y)
                     | otherwise = loop a f

-- ex2.5 (a)
complete :: a -> Int -> Tree a
complete x 0 = (T E x E)
complete x n = (T t x t)
  where
    t = complete x (n - 1)

-- ex2.5 (b)

create:: a -> Int -> Tree a
create x 0 = E
create x n = (T l x r)
  where
    isEven = even n
    ln = if isEven then (n `div` 2) else ((n - 1) `div` 2)
    rn = if isEven then ln - 1 else ln
    l = create x ln
    r = if isEven then create x rn else l

create1:: a -> Int -> Tree a
create1 x 0 = E
create1 x n | odd n     = (T l x l) 
            | otherwise = (T l x b)
  where 
    subsize | odd n     = (n - 1) `div` 2
            | otherwise = (n `div` 2) - 1
    (l, b) = create2 x subsize

create2 :: a -> Int -> (Tree a, Tree a)
create2 x 0 = (E, (T E x E))
create2 x m | m < 0 = error "create2"
            | otherwise = (lesser, greater)
  where
    subsize | odd m      = (m `div` 2) 
            | otherwise =  (m `div` 2) - 1
    (l, b) = create2 x subsize
    lesser | odd m     = (T l x l)
           | otherwise = (T l x g)
    greater| odd m     = (T l x g)
           | otherwise = (T g x g)