A try on a bank machine algorithm...
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
On Sun, May 31, 2009 at 2:19 PM, 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
_______________________________________________ Beginners mailing list Beginners@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
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
On Mon, Jun 01, 2009 at 10:55:30AM -0400, Thomas Friedrich wrote:
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.
It sounded to me a little different: like if you withdraw 200 €, you don't just want a 200 € bill, you want some small bills too: so you would get two 5s, two 10s, a 20, a 50, and a 100. -Brent
Hi,
Ok, I don't really think I know what you are planing to do. cashout 175 [200,100,50,20,10,5] == [0,1,1,1,0,1]
It sounded to me a little different: like if you withdraw 200 €, you don't just want a 200 € bill, you want some small bills too: so you would get two 5s, two 10s, a 20, a 50, and a 100.
thank you so far. Yes, Brent, you are right. I wanted to do what my program does, and moreover become a better Haskell programmer. So even if I could not explain myself to Thomas on the first attempt, I honestly like to study his very short and efficient code in my attempt to get a feeling for "good" code. Thanks for all your help, Bernhard
like to study his very short and efficient code in my attempt to get a feeling for "good" code.
Now I feel embarrassed. I should therefore mention that it is in fact not a very good idea to let the code crash, whenever its not able to cash out any money. I mean that would be a really bad idea. In such a case, you might want to wrap the whole thing with the Maybe monad. import Control.Monad saverCashout :: (Integral a) => a -> [a] -> Maybe [a] saverCashout 0 _ = Just [] saverCashout _ [] = Nothing saverCashout tocash (b:bs) = liftM (fst r :) (saverCashout (snd r) bs) where r = tocash `divMod` b I was just lazy in the other code. *Main> saverCashout 755 [50,100,50,5] Just [15,0,0,1] *Main> saverCashout 801 [50,100,50,5] Nothing Thomas
participants (4)
-
Alexander Dunlap -
Bernhard Lehnert -
Brent Yorgey -
Thomas Friedrich