> module Assignment2 where

The first part of this assignment considers the integer
representations discussed in the first assignment.

1. Make both the long integer and sparse integer representations
   developed in Assignment 1 proper data types.  Then make these types
   instances of the type class Integral.

   Note that in order to be able to perform this instantiation you
   also need to make the types instances of other classes.  It is your
   responsibility to discover and implement all the necessary
   instances.

> data LongInt = Long [Integer]
> data SparseInt = Sparse [(Integer,Integer)]

    We start by providing printouts as integers to long and sparse
    integers.  Not required but nice to have.

> instance Show LongInt where
>     show (Long xs) = foldr (\x s -> s ++ show x) [] xs

> instance Show SparseInt where
>    show (Sparse xs) = show (sparseToInt xs)

    It is tempting to just derive the instances of Eq and Ord, but
    that will not work for sparse integers, where the digits can
    appear in any order.  For Eq I am simply going to compare the
    string representation of the respective numbers.

> instance Eq SparseInt where
>     a == b = show a == show b

> instance Eq LongInt where
>     a == b = show a == show b

    For Ord comparing string representations no longer suffices.
    However, for this assignment nobody said I cannot just convert the
    long and sparse to Integer, so I am going to do just that (in the
    interest of brevity of course, not because I am lazy).

> instance Ord LongInt where
>     a <= b = longToInt a <= longToInt b

> instance Ord SparseInt where
>     (Sparse a) <= (Sparse b) = sparseToInt a <= sparseToInt b

    The Enum instances are just based in the fact that our long and
    sparse integers are both representations of integers:

> instance Enum LongInt where
>     toEnum n = Long (intToLong (fromIntegral n))
>     fromEnum ns = fromIntegral (longToInt ns)

> instance Enum SparseInt where
>     toEnum n = longToSparse (Long (intToLong (fromIntegral n)))
>     fromEnum ns = fromIntegral (longToInt (sparseToLong ns))

    Now I will make long and sparse integers numbers.  The actual
    functions that implement the operations are copied and pasted from
    the previous assignment, see below.

> instance Num LongInt where
>     (Long a) + (Long b) = Long (longAdd a b)
>     (Long a) * (Long b) = Long (longMul a b)
>     fromInteger x = Long (intToLong x)
>     -- Our integers can only be positive
>     abs x = x
>     signum x = 1
>     -- We need to roll subtraction by hand:
>     (Long a) - (Long b) = Long (longSub a b)

    To make sparse integers numbers easy I am going convert them to
    long integers and then perform the actual operations.  This is by
    no means the most elegant of efficient way to go, but will do for
    this assignment and has the merit of reusing the existing
    definitions.

> instance Num SparseInt where
>     a + b = longToSparse ((sparseToLong a) + (sparseToLong b))
>     a * b = longToSparse ((sparseToLong a) * (sparseToLong b))
>     fromInteger x = longToSparse (Long (intToLong x))
>     -- Our integers can only be positive
>     abs x = x
>     signum x = 1
>     -- We need to roll subtraction by hand:
>     a - b = longToSparse ((sparseToLong a) - (sparseToLong b))

    Most actual operations over long integers happen over lists of
    numbers:

> instance Real LongInt where
>     toRational = toRational . longToInt

> instance Real SparseInt where
>     toRational = toRational . longToInt . sparseToLong

    Again, nobody says in this assignment that I cannot just convert
    the long and sparse integers to Integer so in the interest of
    brevity I am going to go the lazy way.

> instance Integral LongInt where
>     quotRem x y = (Long (intToLong (div a b)), Long (intToLong (mod a b)))
>       where a = longToInt x
>             b = longToInt y
>     toInteger = longToInt

> instance Integral SparseInt where
>     quotRem (Sparse x) (Sparse y) = (longToSparse (Long (intToLong (div a b))),
>                                      longToSparse (Long (intToLong (mod a b))))
>       where a = sparseToInt x
>             b = sparseToInt y
>     toInteger = longToInt . sparseToLong

    We reuse many definitions from the first assignment, with minor
    changes in types, and two additional functions:

> longToInt :: LongInt -> Integer
> longToInt (Long xs) = foldr (\ x n -> x + 10 * n) 0 xs
>
> intToLong :: Integer -> [Integer]
> intToLong 0 = []
> intToLong n | n > 0 = (rem n 10) : intToLong (div n 10)
>
> -- Additional function
> sparseToInt :: [(Integer, Integer)] -> Integer
> sparseToInt [] = 0
> sparseToInt ((e,d):xs) = 10^e * d + sparseToInt xs
>
> longIntSort :: [(Integer, Integer)] -> [(Integer, Integer)]
> longIntSort [] = []
> longIntSort (x:xs) = longIntSort [y | y <- xs, lt y x] ++ [x] ++ longIntSort [y | y <- xs, not (lt y x)]
>   where lt (xi, ni) (xj, nj) = xi <= xj
>
> longIntExpand :: [(Integer, Integer)] -> [(Integer, Integer)]
> longIntExpand [] = []
> longIntExpand as = longIntExpand' as 0
>   where longIntExpand' [(i,a)]    last = addZ last i ++ [(i,a)]
>         longIntExpand' ((i,a):as) last = addZ last i ++ [(i,a)] ++ longIntExpand' as (i+1)
>         addZ i j = [ (k,0) | k <- [i .. j-1] ]
>
> longIntList :: [(Integer, Integer)] -> [Integer]
> longIntList = map snd
>
> sparseToLong :: SparseInt -> LongInt
> sparseToLong (Sparse xs) = Long ((longIntList . longIntExpand . longIntSort) xs)
>
> longToSparse :: LongInt -> SparseInt
> longToSparse (Long as) = Sparse (filter (\ (i,a) -> not (a == 0)) (zip [0 .. ] as))
>
> longAdd :: [Integer] -> [Integer] -> [Integer]
> longAdd xs ys = longAdd' xs ys 0
>     where longAdd' [] ys 0 = ys
>           longAdd' [] ys c = longAdd' [c] ys 0
>           longAdd' xs [] 0 = xs
>           longAdd' xs [] c = longAdd' xs [c] 0
>           longAdd' (x:xs) (y:ys) c = (rem (x+y+c) 10) : longAdd' xs ys (div (x+y+c) 10)
>
> longScale :: [Integer] -> Integer -> [Integer]
> longScale xs n
>   | n == 0 = []
>   | n > 0 = longScale' xs n 0
>   where longScale' [] n 0 = []
>         longScale' [] n c = [c]
>         longScale' (x:xs) n c = (rem (x*n+c) 10) : longScale' xs n (div (x*n+c) 10)
>
> longMul :: [Integer] -> [Integer] -> [Integer]
> longMul xs ys = foldr (\x p -> longAdd (longScale ys x) (0 : p)) [] xs
>
> -- Additional function
> longSub :: [Integer] -> [Integer] -> [Integer]
> longSub xs ys = longSub' xs ys 0
>     where longSub' xs [] 0 = xs
>           longSub' xs [] c = longSub' xs [c] 0
>           longSub' (x:xs) (y:ys) c
>             | x >= (y+c) = (x-y-c) : longSub' xs ys 0
>             | otherwise = (x+10)-y-c : longSub' xs ys 1

The second part of the assignment is about binary search trees.  An
implementation of such trees is available on the course's Web site.
You are now asked to modify this implementation as follows:

2. Define a type class Ordered that defines a binary search tree-like
   interface.  That is, the interface should include the functions
   insert (for inserting a new value), member (for finding out whether
   a given value exists), findMin and findMax (which return the
   minimum and the maximum value, respectively), delete (for removing
   a value) and trav (for traversing the stored values thus returning
   a sorted list).  Provide partial implementations of these functions
   if possible.

    Note: traverse is actually taken hence the new name "trav", sorry
    about that.

> class Ordered t where
>     insert :: Ord a => a -> t a -> t a
>     member :: Ord a => a -> t a -> Bool
>     findMin, findMax :: Ord a => t a -> a
>     delete :: Ord a => a -> t a -> t a
>     trav :: Ord a => t a -> [a]

    I cannot think of any partial implementation.

    I should have been able to define the class without the Ord a
    constraints in the individual types and then instantiate it as

    instance (Ord a) => Ordered (BST a) where
        ...

    but for some strange reason that does not work.  I am still
    investigating.

3. Make then the type BST an instance of Ordered.

    From the handout:

> data BST a = Nil | Node a (BST a) (BST a)
>
> instance Show a => Show (BST a) where
>     show t = show' t 0
>         where show' :: Show a => BST a -> Int -> [Char]
>               show' Nil          n = ""
>               show' (Node x l r) n = show' r (n+1) ++ 
>                                      take (n * 4) [' ',' '..] ++ show x ++ "\n" ++ 
>                                      show' l (n+1)

    Now for the actual instance:

> instance Ordered BST where
> 
>     -- rest is copied from the handout
> 
>     insert x Nil          = Node x Nil Nil
>     insert x (Node y l r) | x <= y    = Node y (insert x l) r
>                           | otherwise = Node y l (insert x r)
> 
>     member x Nil          = False
>     member x (Node y l r) | x == y    = True
>                           | x <= y    = member x l
>                           | otherwise = member x r
>     
>     findMin (Node y Nil r) = y
>     findMin (Node y l   r) = findMin l
>     
>     findMax (Node y l Nil) = y
>     findMax (Node y l r)   = findMax r
>     
>     delete v Nil          = Nil
>     delete v (Node x l r) | v == x =    delete' (Node x l r)
>                           | v <= x =    Node x (delete v l) r
>                           | otherwise = Node x l (delete v r)
>         where delete' (Node x Nil r) = r
>               delete' (Node x l Nil) = l
>               delete' (Node x l r) = 
>                   let maxMin = findMax l 
>                   in Node maxMin (delete maxMin l) r
>
>     trav Nil          = []
>     trav (Node y l r) = trav l ++ [y] ++ trav r

Note in passing that the binary search trees are not the only
potential instance of Ordered.  B-trees are the first additional
example that comes to mind.