-- 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.
-- 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. :)
