SICP exercises in Haskell (Section 2.2.1)

-- Section 2.2.1

-- Exercise 2.17

last_pair :: [a] -> [a]

last_pair (x:[]) = [x]

last_pair (x:xs) = last_pair xs

-- Exercise 2.18

reverse' :: [a] -> [a]

reverse' xs = reverse'' xs []

  where reverse'' [] ys = ys

        reverse'' (x:xs) ys = reverse'' xs (x:ys)

        

-- Exercise 2.19        

cc :: (Num a, Ord a) => a -> [a] -> Int

cc amount coin_values

  | amount == 0 = 1

  | amount < 0 || no_more coin_values = 0

  | otherwise = cc amount 

                   (except_first_denomination coin_values)

                + cc (amount - 

                        (first_denomination coin_values)) 

                      coin_values

                

first_denomination :: [a] -> a

first_denomination = head

except_first_denomination :: [a] -> [a]

except_first_denomination = tail

no_more :: [a] -> Bool

no_more = null

Q: Does the order of the list coin-values affect the answer produced by cc? Why or why not? 

A: No, it won't. The algorithm is:

The number of ways to change amount a using n kinds of coins equals

• the number of ways to change amount a using all but the first kind of coin, plus
• the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

So, the order of the coin-values doesn't matter.

-- Exercise 2.20
-- The variadic function in Haskell is a little complicated.
-- See http://okmij.org/ftp/Haskell/polyvariadic.html#polyvar-fn
-- I skip this problem this time, and fix it later.


-- Exercise 2.21
square_list :: [Int] -> [Int]
square_list = map (^2)


-- Exercise 2.22
-- It's a inversed list because of the behavior of cons.
-- Cons always put the later value into the front of the list.
 

-- To be continued. :)