CODEWITHSUNDEEP
clojure
Matthew
Matthew

Reputation: 11613

Return first item in a map/list/sequence that satisfies a predicate

I am looking for a function that returns the first element in a sequence for which an fn evaluates to true. For example:

(first-map (fn [x] (= x 1)) '(3 4 1))

The above fake function should return 1 (the last element in the list). Is there something like this in Clojure?

Upvotes: 70

Views: 42521

Answers (7)

Jim Newton
Jim Newton

Reputation: 652

The way I do this in clojure is sort like you might do it in Scheme.

(defn call-with-found
  "Call the given predicate, pred, on successive elements of the collection
  until the first time pred returns a truthy value, at which time if-found
  is called with that element of the collection, and call-with-found returns
  the return value of if-found.   If no such element of collection is found
  (including if collection is empty) then the value if-not-found (defaulting
  to false) is returned."
  ([pred coll & {:keys [if-found if-not-found]
                 :or {if-found (constantly true)
                      if-not-found false}}]
   (reduce (fn [_ item]
             (if (pred item)
               (reduced (if-found item))
               if-not-found)) if-not-found coll)))

The function call-with-found is called with a predicate and a collection. We search the collection until we find an element which satisfies the predicate, at which point we call the if-found continuation with that value, else we return the if-not-found value.

Upvotes: 0

Casey
Casey

Reputation: 6326

In 2016 there was a patch submitted to clojure core that added an efficient shortcut for (first (filter pred coll)) idiom, it was called seek.

The implementation avoided problems in herent with both the (first (filter)) and (some #(when (pred))) alternatives. That is, it works efficiently with chunked sequences and plays nice with nil? and false? predicates.

Patch:

(defn seek
  "Returns first item from coll for which (pred item) returns true.
   Returns nil if no such item is present, or the not-found value if supplied."
  {:added  "1.9" ; note, this was never accepted into clojure core
   :static true}
  ([pred coll] (seek pred coll nil))
  ([pred coll not-found]
   (reduce (fn [_ x]
             (if (pred x)
               (reduced x)
               not-found))
           not-found coll)))

Examples:

(seek odd? (range)) => 1
(seek pos? [-1 1]) => 1
(seek pos? [-1 -2] ::not-found) => ::not-found
(seek nil? [1 2 nil 3] ::not-found) => nil

Eventually the patch was rejected:

Upon review, we've decided that we do not wish to include this. Use of linear search (and in particular nested linear search) leads to poor performance - often it's better to use other kinds of data structures and that's why this functionality has not been included in the past. ~Alex Miller 12/May/17 3:34 PM

Upvotes: 16

WIZARDELF
WIZARDELF

Reputation: 3885

I tried several methods mentioned in this thread (JDK 8 and Clojure 1.7), and did some benchmark tests:

repl> (defn find-first
         [f coll]
         (first (filter f coll)))
#'cenx.parker.strategies.vzw.repl/find-first

repl> (time (find-first #(= % 50000000) (range)))
"Elapsed time: 5799.41122 msecs"
50000000

repl> (time (some #{50000000} (range)))
"Elapsed time: 4386.256124 msecs"
50000000

repl> (time (reduce #(when (= %2 50000000) (reduced %2)) nil (range)))
"Elapsed time: 993.267553 msecs"
50000000

The results show that reduce way may be the most efficient solution as in clojure 1.7.

Upvotes: 27

Dimagog
Dimagog

Reputation: 1925

Using drop-while instead of filter should address "over-application" of f for chunked sequences:

(defn find-first [f coll]
  (first (drop-while (complement f) coll)))
;;=> #'user/find-first

(find-first #(= % 1) [3 4 1])
;;=> 1

Upvotes: 7

Marko Topolnik
Marko Topolnik

Reputation: 200158

In your case, the idiom is 

(some #{1} [1 2 3 4])

How it works: #{1} is a set literal. A set is also a function evaluating to its arg if the arg is present in the set and to nil otherwise. Any set element is a "truthy" value (well, except for a boolean false, but that's a rarity in a set). some returns the return value of the predicate evaluated against the first collection member for which the result was truthy.

Upvotes: 58

deprecated
deprecated

Reputation: 5242

I think some is the best tool for the job:

(some #(if (= % 1) %) '(3 4 1))

Upvotes: 12

kotarak
kotarak

Reputation: 17299

user=> (defn find-first
         [f coll]
         (first (filter f coll)))
#'user/find-first
user=> (find-first #(= % 1) [3 4 1])
1

Edit: A concurrency. :) No. It does not apply f to the whole list. Only to the elements up to the first matching one due to laziness of filter.

Upvotes: 84

Related Questions