Simple problem from Hudak's SOE

M. Parker mparker@texasycl.org
Mon, 24 Feb 2003 11:34:51 +0000


Thanks, Dean. I understand foldl a lot better now after working through y=
our=20
higher order solution. I checked out the type of "snd" in hugs and basica=
lly=20
figured out what it does, but I was wondering where I could find the=20
definition of this function. Is it possible to look at it in hugs?

Thanks,
Matt

On Sunday 23 February 2003 12:16 am, Dean Herington wrote:
> On Fri, 21 Feb 2003, M. Parker wrote:
> > I'm a real newbie to Haskell, and I'm having trouble with a particula=
r
> > 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)=
=2E
> > For example, make Change 99 [5,1] =09=3D=3D> [19,4]
> >
> > This chapter is about higher order functions, so I'm assuming he want=
s 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 =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
> > functions defined in the chapter. So is it possible to solve this pro=
blem
> > 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 latt=
er
> > leads to clearer and more concise solutions. Although solution 1 is m=
ore
> > 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 functi=
ons.
> > 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 _   []     =3D []
> makeChange1 amt (c:cs) =3D q : makeChange1 r cs
>  where (q,r) =3D amt `quotRem` c
>
> makeChange2 amt coins =3D reverse (snd (foldl f (amt,[]) coins))
>  where f (amt,cnts) coin =3D (r,q:cnts)
>         where (q,r) =3D 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe