{"id":333,"date":"2007-07-08T05:48:00","date_gmt":"2007-07-08T12:48:00","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=333"},"modified":"2007-07-29T12:38:21","modified_gmt":"2007-07-29T19:38:21","slug":"haskell-problem","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=333","title":{"rendered":"Haskell problem"},"content":{"rendered":"<p>Define a function <tt>makeChange<\/tt> that, given a nonnegative integer amount and a list of coin denominations, returns a list of the number of coins of each denomination required to make up the amount. For example:<\/p>\n<p><tt>makeChange 99 [5,1] =&gt; [19,4]<\/tt><\/p>\n<p>i.e. 19 nickels and 4 pennies equals 99 cents. To make life easier, you may assume that the list of denominations is in descending order, and that the penny is always included.<\/p>\n<p>I have the following, which works:<\/p>\n<pre>makeChange :: Int -&gt; [Int] -&gt; [Int]\r\nmakeChange _ [] = []\r\nmakeChange amt (v:vs) = n : (makeChange newamt vs)\r\n    where n = amt `div` v\r\n          newamt = amt - n * v<\/pre>\n<p>However, the problem is at the end of a chapter about using higher order functions like <tt>map<\/tt>, <tt>foldl<\/tt>, <tt>foldr<\/tt>, <tt>zip<\/tt>, etc. I have a feeling there&#8217;s a way to do this problem that way too. But it&#8217;s late and Mrs Elbeno is calling me to bed. AOAP.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Define a function makeChange that, given a nonnegative integer amount and a list of coin denominations, returns a list of the number of coins of each denomination required to make up the amount. For example: makeChange 99 [5,1] =&gt; [19,4] i.e. 19 nickels and 4 pennies equals 99 cents. To&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-333","post","type-post","status-publish","format-standard","hentry","category-haskell"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=333"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/333\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}