[Haskell-beginners] A try on a bank machine algorithm...

[Alexander Dunlap]

On Sun, May 31, 2009 at 2:19 PM, Bernhard Lehnert <b.lehnert at gmx.de> wrote:
> Hi,
>
> in a Python Forum someone came up with his homework. Just beginning to
> learn Haskell I thougt I give it a try. I came up with a working
> function that I present here to ask you, if I am doing this right or how
> I could do better.
>
> The job was: A cash machine has to compute the division of bank notes
> for any given amount of money.
> According to German wikipedia a common algorithm is to start giving one
> 5$ bill, one 10$ and so on as long as possible (I call this uphill).
> After that the maximum possible amount of large bank notes is given...
>
> Thus every customer gets some small bills and still the number of bills
> is limited. My answer is a function called 'paymixture' which first
> calls a function 'uphill' and afterwards a function 'downhill', each of
> which realizes one part of the above mentioned algorithm. The downhill
> function might also be usefull apart from the rest which is why
> indentation ist different...
>
> Thanks a lot,
> Bernhard
> -------------------------------------------------------------
> paymixture :: (Ord t, Num t)=> t->[t]->[t]
> -- usage: paymixture (sum to pay) (list of possible bills)
> -- list of bills has to be sorted, like in
> -- 'paymixture 175 [5,10,20,50,100]'
> -- last element of the returned list is what could not be paid.
>
> paymixture n list = init(up) ++ down
>       where
>       up = uphill n list
>       down = downhill (last(up)) (reverse list)
>
>       uphill :: (Ord t, Num t)=> t->[t]->[t]
>       uphill n [] = [n]
>       uphill 0 _  = [0]
>       uphill n (x:xs) = if n>=x then x : uphill (n-x) xs
>                             else uphill n xs
>
> downhill :: (Ord t, Num t)=> t ->[t]->[t]
> -- usage: downhill (sum to pay) (list of possible bills)
> -- list if bills has to be reverse sorted, like e. g.
> -- 'downhill 175 [200, 100, 50, 20, 10,5]'
> -- last elemt of return value is the rest that could
> -- not be paid.
>
> downhill n supply | (n<last supply) = [n]
>                  | otherwise = max : downhill (n-max) supply
>                     where max = head([x|x<-supply, x<=n])
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>

Some comments on things that would be done differently by someone with
more experience:

- You have more parentheses than you need. If you have head xs, it
doesn't need to be head(xs). Parentheses are only needed when you want
it to associate in the other direction (i.e. you need them for head
(tail xs) but not take 3 xs because 3 and xs are both arguments of
take but (tail xs) is one argument of head. It's actually even more
complicated than that when you get into currying (although it makes a
lot more sense then) but that's the simple way of thinking about it.
- The "last" function is terribly inefficient - it has to traverse the
entire list to get to the end. It would be better for uphill to return
a pair of (all-but-last-element,last-element) because then the list
wouldn't have to be traversed again to get the last element.

It looks like you're doing well; good luck learning Haskell!

Alex