# Finding first match in recursive search

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?

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).

• ah, (some) is exactly what I am looking for. As for performance issues, I have several ideas for algorithms I would like to try, and to be able to compare the relative performance of these, atleast I need to make sure that they are not doing any un-neccessary work. (My current example is solving sudoku, and I am pretty sure there is only one solution to each puzzle, ie. it is futile to search for more solutions after finding one). – Rolf Rander Mar 19 '13 at 14:28

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.

• Hm, but I need the result of do-something (that will be my solved sudoku-board), so wouldn't I need to do: (first (drop-while nil? (map do-something range))) – Rolf Rander Mar 17 '13 at 20:00
• In that case, you can just call do-something as the last step (you may need to check non-nil). – Asumu Takikawa Mar 18 '13 at 9:32