How to replace this loop with something more idiomatic?

Question

I've been working through "Clojure for the Brave and True" and I just spent an hour staring at this loop trying to turn it into a reduce or some other "prettier" loop. I'm getting tripped up on trying to hit that target number while in the loop and returning early. The idea here is to randomly generate a number (based on sizes) and return the body-part at that number. Conceptually I'm thinking about breaking the list in two and returning the "break point". I could also imagine mapping over it and adding a "size index" to then filter on. I feel like I'm missing something simple (I kept trying reduce).

(defn hit
  "Expects a sequence of maps which have a :name and :size"
  [body-parts]
  (let [body-part-size-sum (reduce + 0 (map :size body-parts))
       target (inc (rand body-part-size-sum))]
    (loop [[part & rest] body-parts
           accumulated-size (:size part)]
      (if (> accumulated-size target)
         part
        (recur rest (+ accumulated-size (:size part)))))))

Answer 1

The reduced function effectively short-circuits a reduction.

Also I replaced the reduce on + with apply (it is clearer though slightly less efficient)

(defn hit
  "Expects a sequence of maps which have a :name and :size"
  [body-parts]
  (let [body-part-size-sum (apply + (map :size body-parts))
       target (inc (rand body-part-size-sum))
       found (reduce (fn [accumulated-size part]
                        (if (> accumulated-size target)
                          (reduced part)
                          (+ accumulated-size (:size part))))
                     0
                     body-parts)]
    (if (map? found) found)))

The final if is to return nil rather than the accumulated size if a hit never occurs.

Answer 2

I think doing a reductions to get a cumulative sums How to make a cumulative sequence?

and then finding the first that matches the codition http://clojuredocs.org/clojure_contrib/clojure.contrib.seq-utils/find-first

would enable you to get rid of the explicit loop.

Answer 3

One of my early lessons in Clojure was that it is not wrong to use a loop when a loop is the right solution. The original code is not bad and does not necessarily need any improvement.

If you had a lot of weights (sizes), a binary search for the correct interval would be better than the simple linear search. The most Clojure-ish way to do a binary search is probably to make Java do it.

(defn find-interval [intervals x]
  (Math/abs (inc (java.util.Collections/binarySearch intervals x))))

An important functional idiom to learn is closures, or "let over lambda". We can save variables by placing them in the lexical environment of a returned function. In this case, we'll save the precomputed cumulative sum of weights w, their grand total n, and the values we want to choose from in a vector.

(defn weighted-choice-generator [choices]
  (let [weights (java.util.ArrayList. (reductions + (map second choices)))
        values (mapv first choices)
        n (last weights)]
    (fn [] (nth values (find-interval weights (long (rand n)))))))

We'll coerce the sample data to be a sequence of value-weight pairs as expected above and get our hitting function from the weighted-choice-generator.

(def hit-hobbit-asym (weighted-choice-generator 
                       (map (juxt identity :size) asym-hobbit-body-parts)))

And now test thousands of times to confirm hits are in proportion to size:

(pprint (frequencies (repeatedly 59000 hit-hobbit-asym)))
{{:name "left-shoulder", :size 3} 2951,
 {:name "chest", :size 10} 9922,
 {:name "left-forearm", :size 3} 3046,
 {:name "left-lower-leg", :size 3} 3038,
 {:name "neck", :size 2} 1966,
 {:name "back", :size 10} 9900,
 {:name "left-ear", :size 1} 997,
 {:name "nose", :size 1} 1023,
 {:name "left-thigh", :size 4} 4020,
 {:name "left-achilles", :size 1} 972,
 {:name "left-hand", :size 2} 2075,
 {:name "left-foot", :size 2} 2062,
 {:name "left-eye", :size 1} 1047,
 {:name "left-knee", :size 2} 2068,
 {:name "left-upper-arm", :size 3} 2996,
 {:name "abdomen", :size 6} 6020,
 {:name "head", :size 3} 2933,
 {:name "left-kidney", :size 1} 986,
 {:name "mouth", :size 1} 978}