Simple problem from Hudak's SOE

[Dean Herington]

On Fri, 21 Feb 2003, M. Parker wrote:

> I'm a real newbie to Haskell, and I'm having trouble with a particular problem 
> dealing with higher-order functions.
> 
> Exercise 5.9 in Hudak's "School of Expression" asks us to write a function, 
> "makeChange," s.t. it makes change for a given amount using coins in a coin 
> supply (represented by a list of decreasing integers). For example, 
> 	make Change 99 [5,1] 	==> [19,4]
> 
> This chapter is about higher order functions, so I'm assuming he wants us to 
> compute the result using the higher order functions defined in the chapter 
> (map, foldl, foldr). I devised two solutions:
> 
> {-Solution 1-}
> makeChange money coinList =
>     zipWith div (scanl mod money coinList) coinList
> 
> {-Solution 2-}
> makeChange' money (coin:coins) =
>     let money' = money `mod` coin
>         numCoins = money `div` coin
>     in  (numCoins: makeChange' money' coins)
> makeChange' 0 _  = []
> makeChange' _ [] = []
> 
> However, my problem is that neither solution uses the higher-order functions 
> defined in the chapter. So is it possible to solve this problem using map and 
> fold?
> 
> Furthermore, Hudak makes the case that we should strive to find the 
> higher-order solutions instead of the recursive ones because the latter leads 
> to clearer and more concise solutions. Although solution 1 is more concise, I 
> feel like Solution 2 is clearer to me than Solution 1, but maybe this is just 
> because I'm new to haskell and higher order functions. It just seems like its 
> easier to understand the actual algorithm in solution 2 than in solution 1.
> 
> Thanks,
> Matt Parker
> University of North Texas undergrad
> http://www.cs.unt.edu

Here's what I had come up with for that exercise:

makeChange1 _   []     = []
makeChange1 amt (c:cs) = q : makeChange1 r cs
 where (q,r) = amt `quotRem` c

makeChange2 amt coins = reverse (snd (foldl f (amt,[]) coins))
 where f (amt,cnts) coin = (r,q:cnts)
        where (q,r) = amt `quotRem` coin

As you said in comparing your two solutions, I'm not convinced the
higher-order solution is clearer in this case.  (By the way, I do
generally like to use higher-order functions.)

Dean