Simple problem from Hudak's SOE

M. Parker mparker@texasycl.org
Fri, 21 Feb 2003 21:35:02 +0000


I'm a real newbie to Haskell, and I'm having trouble with a particular pr=
oblem=20
dealing with higher-order functions.

Exercise 5.9 in Hudak's "School of Expression" asks us to write a functio=
n,=20
"makeChange," s.t. it makes change for a given amount using coins in a co=
in=20
supply (represented by a list of decreasing integers). For example,=20
=09make Change 99 [5,1] =09=3D=3D> [19,4]

This chapter is about higher order functions, so I'm assuming he wants us=
 to=20
compute the result using the higher order functions defined in the chapte=
r=20
(map, foldl, foldr). I devised two solutions:

{-Solution 1-}
makeChange money coinList =3D
    zipWith div (scanl mod money coinList) coinList

{-Solution 2-}
makeChange' money (coin:coins) =3D
    let money' =3D money `mod` coin
        numCoins =3D money `div` coin
    in  (numCoins: makeChange' money' coins)
makeChange' 0 _  =3D []
makeChange' _ [] =3D []

However, my problem is that neither solution uses the higher-order functi=
ons=20
defined in the chapter. So is it possible to solve this problem using map=
 and=20
fold?

Furthermore, Hudak makes the case that we should strive to find the=20
higher-order solutions instead of the recursive ones because the latter l=
eads=20
to clearer and more concise solutions. Although solution 1 is more concis=
e, I=20
feel like Solution 2 is clearer to me than Solution 1, but maybe this is =
just=20
because I'm new to haskell and higher order functions. It just seems like=
 its=20
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