# Simple problem from Hudak's SOE

Dean Herington heringto@cs.unc.edu
Sat, 22 Feb 2003 19:16:21 -0500 (EST)

```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

```