3
\$\begingroup\$

I'm reluctant to ask this question. My code below works, it's intelligible, and it seems reasonably efficient. It's just that there's a trivial, nitpicky issue that's driving me crazy. The function maxes below collects all elements of a sequence that are "maximum" according to some criterion.

;; Example of use of maxes
;; Collect all maps with the maximum value for `:a`:
(maxes :a [{:a 1 :b 2} {:a 4 :b 5} {:a 5 :b 5} {:b 3 :a 5}])
;;=> [{:b 5, :a 5} {:b 3, :a 5}]

(defn- maxes-helper
  "Helper function for maxes."
  [f s best-val collected]
  (if (empty? s)
    collected
    (let [new-elt (first s)
          new-val (f new-elt)]
      (cond (== new-val best-val) (recur f (rest s) best-val (conj collected new-elt))
            (>  new-val best-val) (recur f (rest s) new-val  [new-elt])
            :else                 (recur f (rest s) best-val collected)))))

(defn maxes
  "Returns a sequence of elements from s, each with the maximum value of (f element)."
  [f s]
  (if (empty? s)
    nil
    (let [new-elt (first s)
          new-val (f new-elt)]
      (maxes-helper f (rest s) new-val [new-elt]))))

What's really bugging me that I have to test for emptiness of the input collection s both in the top-level function and in the tail-recursive helper function. I also want to add a custom exception when (f new-elt) is non-numeric, and so I need to test that twice, both for new-val and for first call to (f new-elt) that becomes the first best. So I've got a trivial amount of duplication of code, and I keep thinking that there must be a way to get rid of the duplication. But I can't see how to do this (without testing that best is numeric on every iteration). Am I missing something obvious (or non-obvious)?

(BTW I wrote another version using reduce, but it's about twice as slow, according to Criterium.)

\$\endgroup\$
2
  • \$\begingroup\$ If that's where it belongs, I'll be happy to move it there. My question is pretty narrow. It looks to me like the focus at Code Review is broader: "Here's my code; how can I improve it?" I think that what I wrote is pretty good, but I'm open to suggestions for entirely different methods. \$\endgroup\$
    – Mars
    Dec 17 '14 at 20:50
  • \$\begingroup\$ My previous comment responded to a comment on StackOverflow. No longer makes sense--feel free to ignore it. \$\endgroup\$
    – Mars
    Dec 18 '14 at 3:44
3
\$\begingroup\$

You don't really need the helper function, the original maxesis pretty much equivalent to call maxes-helper with a sensible MIN_VALUE and empty sequence, so I refactored and joined both for you leveraging multi-arity

   (defn maxes
      "Returns a sequence of elements from s, each with the maximum value of (f element)."
      ([f s]
       (maxes f s Double/NEGATIVE_INFINITY '()))
      ([f s best-val collected]
      (if (empty? s)
        collected
        (let [new-elt (first s)
              new-val (f new-elt)]
          (cond (>  new-val best-val) (recur f (rest s) new-val  [new-elt])
                (== new-val best-val) (recur f (rest s) best-val (conj collected new-elt))
                :else                 (recur f (rest s) best-val collected))))))

Edited to replace nil by Double/NEGATIVE_INFINITY as suggested by @fmikes

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Double/NEGATIVE_INFINITY is an interesting MIN_VALUE. (It lets you eliminate the nil? check.) \$\endgroup\$
    – mfikes
    Dec 17 '14 at 21:41
  • \$\begingroup\$ That's beautiful. Thank you, James Sharp and @mfikes. \$\endgroup\$
    – Mars
    Dec 18 '14 at 2:51

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.