4
\$\begingroup\$

I'm learning Clojure and have written a small function to calculate change. I don't like few things about the code and would primarily like to replace recursive call with something more idiomatic. Could you please comment on the code and suggest a better (more Clojure-like) way of implementing it?

(def in-bank #{1 2 5 10})

(defn smaller-than? [compare-input metric]
  (>= compare-input metric))

(defn get-max-smaller-than [input]
  (apply max (filter (partial smaller-than? input) in-bank)))

(defn change-calc [change-requested change-given]
  (let [calculated
    (get-max-smaller-than change-requested)]
    (let [upd-change-given
      (conj change-given calculated)]
        (let [sub-request (- change-requested calculated)]
          (if (= sub-request 0)
            upd-change-given (recur sub-request upd-change-given))))))
\$\endgroup\$
4
\$\begingroup\$

First, there is nothing wrong with your recursive call: recur is about as idiomatic as Clojure gets.

Now, let's try to improve your code.

  • If you look at it, smaller-than? is a synonym for >=. It just passes it the same arguments in the same order.

You could define it as ...

(def smaller-than? >=)

... or, better, just use >=. If you want your own name, you'd have been better to call it not-smaller-than?.

  • There is no need to nest lets in change-calc. One let will do. Successive bindings in a let are evaluated in order.
  • Try to choose suggestive names. I'd replace the meaningless calculated with something like candidate.

Thus we get

(defn max-smaller-than [input]
  (apply max (filter (partial >= input) in-bank)))

(defn change-calc [change-requested change-given]
  (let [candidate (max-smaller-than change-requested)
        upd-change-given (conj change-given candidate)
        sub-request (- change-requested candidate)]
          (if (= sub-request 0)
            upd-change-given (recur sub-request upd-change-given))))

There are a couple of worries here:

  • We'd better deal with a zero change-requested directly than work out it's going to be zero next time round.
  • The test for sub-request is for exactly zero. What happens if we can't give exact change? (With 1 in in-bank, this will not arise. But if it ever does, max throws an arity exception).

These revisions get us to

(defn change-calc [change-requested change-given]
  (if (pos? change-requested)
    (let [candidate (max-smaller-than change-requested)
          upd-change-given (conj change-given candidate)
          sub-request (- change-requested candidate)]
      (recur sub-request upd-change-given))
    change-given))

But this doesn't deal with the exception throwing problem. What is perhaps a better solution to this follows.


Let's look at the problem afresh.

Your code returns

  • its second (sequence) argument with ...
  • the change from the in-bank denominations conj-ed onto it, so at the front/back if the sequence is a list/vector.

In any programming language, the second function should be distinct: especially in Clojure, where it is easy to append to a vector.

How do we do it?

  • For the change, we can return a count of how many coins there are of each denomination, using a map from denomination to number. If Clojure had a standard multiset/bag, we'd use it instead.
  • And let's make the denomination set an explicit argument.

If we want to make up a sum from a number of denominations, we can do the following:

(defn change [sum denoms]
  (reduce
    (fn [[ans ch :as both] d]
      (let [c (quot ch d)]
        (if (zero? c) both [(assoc ans d c) (mod ch d)])))
     [{} sum]
     (sort > denoms)))

This is more or less the algorithm you wrote, with a few wrinkles:

  • We sort the denominations in decreasing order.
  • We deal with each once and for all through a reduce.
  • We use quot and mod to short-circuit a loop using subtraction.

The result is a pair:

  • a map representing a multiset of how many (non-zero) there are of each denomination, and
  • a number for how much change is left over unreconciled.

Examples:

(change 8 in-bank)
;[{1 1, 2 1, 5 1} 0]

(change 8 #{2 5 10})
;[{2 1, 5 1} 1]

(change 13 #{1 5 10})
;[{1 3, 10 1} 0]
  • The idea of returning the residue too arose from the algorithm, where it is part of the working.
  • If 1 is a denomination, the residue is always 0.
  • A development might be to know how many of each coin were present to start with.
\$\endgroup\$
2
\$\begingroup\$

One thing to note is that you dont have to use 3 different let statements, you could just use one instead (each new 2-tuple in the let binding group is aware to all its previous bindings).

Another thing, you might not want to expose 'change-given' to the user, since it generally has to be an empty list, so you could "confine" your recursion using the loop macro, like this:

(defn change-calc [change-requested]
  (loop [change-requested change-requested change-given []]
    (let [calculated       (get-max-smaller-than change-requested)
          upd-change-given (conj change-given calculated)
          sub-request      (- change-requested calculated)]
      (if (zero? sub-request)
        upd-change-given
        (recur sub-request upd-change-given)))))

If you really wanted to get rid of explicit recursion, you could always use implicit one, using methods such as reduce and iterate. here is an example:

(defn change-calc [change-requested]
  (second
   (last
    (take-while (complement nil?)
                (iterate (fn[[n coins]]
                           (when (pos? n)
                             (let [coin (get-max-smaller-than n)]
                               [(- n coin) (cons coin coins)]))) [change-requested []])))))

reduce is a catamorphism, which informally shrinks a list into a number. You are looking for the reverse operation, blowing a number into a list, this is called anamorphism. You could read this interesting blog post about anamorphisms in clojure

\$\endgroup\$
  • \$\begingroup\$ This applies a set of numbers (the implicit denominations argument) to a number and produces a multiset/bag of numbers, albeit not recognised as such in the code. \$\endgroup\$ – Thumbnail Nov 19 '14 at 16:54
0
\$\begingroup\$

Slightly modified version using loop-recur. Use vector for in-bank to find biggest denom faster. You are using set and filter+max which do a lot more work than filter+first.

(def in-bank [10 5 2 1])

(defn change-calc [n]
  (loop [rem n change []]
    (if-let [sm (first (filter (partial >= rem) in-bank))]
      (recur (- rem sm) (conj change sm))
      change)))

To answer how is this better, using criterium bench original code clocks in 15ms, my code - 7.5ms for (change-calc 99999) Using vector for in-bank fit better here.

\$\endgroup\$
  • 1
    \$\begingroup\$ why is it better than the original post? \$\endgroup\$ – Malachi Nov 18 '14 at 22:30
  • \$\begingroup\$ @Malachi it's shorter and easier to read. \$\endgroup\$ – edbond Nov 19 '14 at 12:09
  • \$\begingroup\$ also note that in-bank is a vector and don't need to filter and apply max and find first instead. \$\endgroup\$ – edbond Nov 19 '14 at 12:10
  • \$\begingroup\$ so your review of the original post is "use a vector it's faster" ? this isn't a good review, you should explain how it makes the code faster and better. \$\endgroup\$ – Malachi Nov 19 '14 at 14:15
  • \$\begingroup\$ @Malachi yes, it's the answer to "suggest a better (more Clojure-like) way of implementing it". It is more concise, faster and more Clojure-like. \$\endgroup\$ – edbond Nov 19 '14 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.