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

[Bernhard Lehnert]

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])