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
_______________________________________________ Beginners mailing list Beginners@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