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