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

[Thomas Friedrich]

Bernhard Lehnert 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
>   


Ok, I don't really think I know what you are planing to do. Say I'd like 
to have 175 € form an ATM and [200, 100, 50, 20, 10,5] is the list of 
bills that can be used to cash this money. Do you what to produce a list 
like [0,1,1,1,0,1]? Telling you that you have to take one 100€ bill, one 
50€ bill, etc...

Then I would do it the following:

cashout :: (Integral a) => a -> [a] -> [a]
cashout 0 _ = []
cashout _ [] = error "*** in cashout: Not cashable."
cashout tocash (b:bs) = fst r : cashout (snd r) bs
where r = tocash `divMod` b

prop_cashout tocash bills = tocash == sum (zipWith (*) (cashout tocash 
bills) bills)


Hence,

cashout 175 [200,100,50,20,10,5] == [0,1,1,1,0,1]

But maybe you want something different.

Thomas