Finding first match in recursive search

Question

I am searching a recursive solution space and would like to return the first match I find. (I am using this to solve sudoku, but I guess this would apply to any recursively defined problem or datastructure).

So, in pseudocode, I need to call a function repeatedly with a set of possible input values, and return the first non-nil result:

for each possible input i:
    r = do-something(i)
    if r <> nil:
        return r
return nil

My first attempt was to just translate this into clojure:

(defn find-first
  [func values]
  (loop [v values]
    (if (empty? v)
      nil
      (if-let [ret (func (first v))]
        ret
        (recur (rest v))))))

But whenever I use (loop) it feels like I am programming C and not clojure, so I tried looking at this as applying a function to a sequence and returning the first non-nil result:

(defn find-first-2
  [do-something range]
  (->> range
       (map do-something)
       (remove nil?)
       first))

This looks more like clojure, and should work the same way because of lazy sequences. However, lazy sequences actually chunk items in sets of 32, so when my ranges are shorter than 32 items this isn't really lazy at all.

I have found the "unchunk"-trick creating really lazy sequences, but this also doesn't really "feel" right...

What would be other ways of implementing this?

Answer 1

If the non-nil results of do-something are guaranteed to be logical true, you can easily use some:

(some pred coll)

Returns the first logical true value of (pred x) for any x in coll, else nil. One common idiom is to use a set as pred, for example this will return :fred if :fred is in the sequence, otherwise nil: (some #{:fred} coll)

(defn find-first-3
  [do-something range]
  (some do-something range)
)

If you expect do-something to return false as possible, non-nil value, you could use keep:

(keep f coll)

Returns a lazy sequence of the non-nil results of (f item). Note, this means false return values will be included. f must be free of side-effects.

(defn find-first-4
  [do-something range]
  (first (keep do-something range))
)

As for the chunk-issue: You should not bother if you're not hitting any performance issues or other problems. Otherwise, if you really want to get rid of it, the unchunk-trick you mentioned is totally fine IMHO, until Clojure will offer an official, built-in option (maybe it will someday).

Answer 2

You can use drop-while instead of mapping over the given sequence.

(defn find-first-3 [do-something range]
  (first (drop-while #(nil? (do-something %)) range)))

This should be minimally lazy (since you don't need laziness here), won't traverse unnecessary parts of the list, and concise.