Solutions to Problem Set 2
==========================

Hong Jiang

> module PS2 where

Chapter 5
=========

1. Exercise 5.3 in SOE.

"Rewrite the definition of length nonrecursively."

Solution:

> length' :: [a] -> Int
> length' as = foldr (\x y -> y+1) 0 as


2. Exercise 5.5 in SOE.  You should, of course, use higher-order
   functions rather than direct recursion in solving these.

"Define a function that behaves as each of the following:"

   1. Double each number in a list. For example:
      doubleEach [1,2,3] => [2,4,6]

Solution:

> doubleEach :: Num a => [a] -> [a]
> doubleEach = map (*2)

The above uses currying simplification discussed in Chapter 9.  It
also uses type classes in the type signature to make the type most
general in terms of the kinds of numbers that it can handle, but we
have not discussed type classes yet (they are covered in Chapter 12)!
So it is sufficient to write something like the following instead:

  doubleEach :: [Int] -> [Int]
  doubleEach as = map (*2) as

In the following I will continue to use type classes as well as
currying simplification.

   2. Pairs each element in a list with that number and one plus that
      number. For example:
      pairAndOne [1,2,3] => [(1,2), (2,3), (3,4)]

Solution:

> pairAndOne :: Num a => [a] -> [(a,a)]
> pairAndOne = map (\a -> (a, a+1))

   3. Adds together each pair of numbers in a list. For example:
      addEachPair [(1,2),(3,4),(5,6)] => [3,7,11]
      
Solution:

> addEachPair :: Num a => [(a,a)] -> [a]
> addEachPair = map (\(a, b) -> a + b)

or, using "uncurry" from the standard prelude:

  addEachPair = map (uncurry (+))


3. Exercise 5.7 in SOE.  

"Define a function that adds "pointwise" the elements of a list of
pairs. For example: addPairsPointwise [(1,2),(3,4),(5,6)] => (9,12)."

Solution:

> addPairsPointwise :: Num a => [(a,a)] -> (a,a)
> addPairsPointwise = foldr add' (0,0)
>                     where add' (a, b) (c, d) = (a+c, b+d)


4. Exercise 5.9 in SOE. Note that the straightforward solution to this
   problem is not necessarily optimal for all sets of coin values.
   For example, making change for an amount 6 given coin values
   [4,3,1] is better solved as [0,2,0] rather than [1,0,2]. You are
   not required to give the optimal solution, but feel free to do so
   if you wish.

"Suppose you are given a nonnegative integer amt representing a sum of
money, and a list of coin denominations [v_1, v_2, ..., v_n], each
being a positive integer. Your job is to make change for amt using the
coins in the coin supply. Define a function makeChange to solve this
problem. For example, your function may behave like this:
   
makeChange 99 [5, 1] => [19, 4]

where 99 is the amount and [5,1] represents the types of coins (say,
nickels and pennies in U.S. currency) that we have. The answer [19,4]
means that we can make the exact change with 19 five-unit coins and 4
single-unit coins; this is the best (in terms of the total number of
coins) possible solution.

To make things slightly easier, you may assume that the list
representing the coin denominations is given in descending order, and
that the single-unit coin is always one of the coin types."

Solution:

The following program is more complicated than what is required,
because it gives the optimum solution (uses the fewest coins), and
no assumption about the order of the coin list is made.

> optiList :: [[Integer]] -> [Integer] -- find the optimal solution from 
>                                      -- all possible solutions
> optiList as = foldr minList [] as 
>                  where 
>                    minList as [] = as
>                    minList [] bs = bs
>                    minList as bs = let sum_a = foldr (+) 0 as
>                                        sum_b = foldr (+) 0 bs
>                                    in
>                                      if sum_a < sum_b then as
>				                        else bs
>
> makeChange :: Integer -> [Integer] -> [Integer]
> makeChange 0 cs = map (\x -> 0) cs
> makeChange n cs = let ss = map (makeChange' n cs) cs
>                   in optiList ss
>
> makeChange' :: Integer -> [Integer] -> Integer -> [Integer]
> makeChange' n cs m = 
>       if (n-m >=0) then
>           let sr = makeChange (n - m) cs
>           in makeVector sr cs m
>       else []
>
> makeVector (a:as) (b:bs) m = if m == b then (a+1):as
>                              else a:(makeVector as bs m)
> makeVector [] _ _ = []
> makeVector _ _ _ = error "Impossible."


Chapter 6
=========

5. Define a function squares :: Int -> [Int] such that squares n
   returns a list of all perfect squares less than or equal to n. For
   example, squares 50 returns [1,4,9,16,25,36,49]. Do not use direct
   recursion.

Solution:

> squares :: Int -> [Int]
> squares n = filter (<= n) (map (^2) [1, 2.. n])


6. Using the function iterate from the Standard Prelude (and possibly
   some other higher-order functions that we have already discussed),
   define a function intSeq :: Int -> Int -> Int -> [Int] such that
   intSeq a b c is equivalent to [a, b .. c].

Solution:

  intSeq :: Int -> Int -> Int -> [Int]
  intSeq a b c = take (div (c-a) (b-a) + 1) (iterate (+ (b-a)) a)

The above solution has the problem that b-a may be zero, thus not
allowing for the proper generation of an infinite list.  A better
solution is thus:

> intSeq :: Int -> Int -> Int -> [Int]
> intSeq a b c = takeWhile (<=c) (iterate (+ (b-a)) a)