> module Assignment1 where

In this assignment we will represent arbitrary precision integers in
three ways as follows, where a digit is a number between 0 and 9, and
a strictly positive digit is a number between 1 and 9.

* A native integer is a value of the Haskell type Integer.

* A long integer representation is a list of all the decimal digits of
  an integer, starting with the least significant digit. For example
  the list [1,2,3,4] is the long integer representation of the number
  4321. You may take [] (the empty list) as an alternative long
  representation of the number 0.

> type LongInt = [Integer]

* For some k > 0, k strictly positive integers xi, and k strictly
  positive digits ni, 1 <= i <= k, a sparse integer representation is
  a list of pairs [(x1, n1), (x2, n2), ... , (xk, nk)] that represents
  the number Sum from i=1 to k of ni * 10^xi. Note in passing that []
  is the sole possible sparse representation of 0.

> type SparseInt = [(Integer,Integer)]

We start the assignment by providing conversion functions between the
three representations of integers. For this purpose:

1. Define a function intToLong that converts a native integer into its
   long representation.

> intToLong :: Integer -> LongInt
> intToLong 0 = []
> intToLong n | n > 0 = (rem n 10) : intToLong (div n 10)

2. Use a fold to define a function longToInt that converts a long
   representation of that integer into a native integer.

> longToInt :: LongInt -> Integer
> longToInt xs = foldr (\ x n -> x + 10 * n) 0 xs

3. Modify the Quicksort implementation presented in class so that it
   sorts lists of pairs (x,n) with respect to the first component x,
   thus obtaining the function longIntSort.

> longIntSort :: SparseInt -> SparseInt
> 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
 
4. Define a function longIntExpand that adds the missing (null) digits
   to a number in the sparse integer representation. You can assume
   that the number is already sorted in increasing order of its
   coefficients. For example

     longIntExpand [(1,3),(4,2),(6,1)]

   should evaluate to [(0,0),(1,3),(2,0),(3,0),(4,2),(5,0),(6,1)].

> longIntExpand :: SparseInt -> SparseInt
> 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] ]

5. Use a map to define a function longIntList that receives the output
   of longIntExpand and drops the exponents, thus obtaining the long
   integer representation of the number. For example:

     longIntList [(0,0),(1,3),(2,0),(3,0),(4,2),(5,0),(6,1)]

   should evaluate to [0,3,0,0,2,0,1].

> longIntList :: SparseInt -> LongInt
> longIntList = map snd

6. Put all the functions above together to define the function
   sparseToLong that receives a sparse representation of an integer
   and evaluates to the long representation of that integer.  For
   example:

     sparseToLong [(1,3),(4,2),(6,1)]

   should evaluate to [0,3,0,0,2,0,1].

> sparseToLong :: SparseInt -> LongInt
> sparseToLong = longIntList . longIntExpand . longIntSort

7. Use a zip and a filter to define one more function longToSparse
   that receives the long representation of an integer and returns a
   sparse representation of that integer. For example:

     longToSparse [0,3,0,2,0,1]

   should evaluate to [(1,3),(3,2),(5,1)] or any permutation thereof
   (at your discretion).

> longToSparse :: LongInt -> SparseInt
> longToSparse as = filter (\ (i,a) -> not (a == 0)) (zip [0 .. ] as )

8. Define a function longAdd n m that returns the sum of n and m. For
   example,

     longAdd [1,5,3] [9,6,7]

   should evaluate to [0,2,1,1] (since 351 + 769 = 1120).

> longAdd :: LongInt -> LongInt -> LongInt 
> 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)

9. Define a function longScale n d that multiplies the long
   representation n with the single digit d. For example,

     longScale [1,2,3,4] 4

   should evaluate to [4,8,2,7,1].

> longScale :: LongInt -> Integer -> LongInt 
> 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)

10. Use a fold to define a function longMul n m that returns the
    product of n and m. For example:

      longMul [1,2,3] [4,5,6]

    should evaluate to [4,3,9,9,0,2] (since 321 × 654 = 209934).

    Hint. It may be easier to start by writing a plain recursive
    function longMul and use that as an inspiration for your folding
    implementation.

> longMul,longMul' :: LongInt -> LongInt -> LongInt

Plain recursive longMul' is going to help me decide the operation to
be applied via the fold:

> longMul' [] ys = []
> longMul' (x:xs) ys = longAdd (longScale ys x) (0 : longMul xs ys)

Now I am ready to state the function as specified (using a fold):

> longMul xs ys = foldr (\x p -> longAdd (longScale ys x) (0 : p)) [] xs

Important notes

The use of programming techniques (folds, maps, and so on) is
mandatory whenever specified in the handout. For your convenience
these requirements are emphasized throughout the handout.

Provide suitable type definitions for all your top level
functions. Use the type [Integer] for long integer representations and
[(Integer,Integer)] for the sparse representation (I know that it can
be argued that Int would make more sense in two instances, but such a
type definition can be realized with fewer headaches). Your type
definitions must be as specific as you can make them.  In particular
just copying the output of :type commands into your script will be
penalized.