Find First Element in a Sequence That Matches a Predicate

Find first element in a sequence that matches a predicate

To find the first element in a sequence seq that matches a predicate:

next(x for x in seq if predicate(x))

Or simply:

Python 2:

next(itertools.ifilter(predicate, seq))

Python 3:

next(filter(predicate, seq))

These will raise a StopIteration exception if the predicate does not match for any element.

---

To return None if there is no such element:

next((x for x in seq if predicate(x)), None)

Or:

next(filter(predicate, seq), None)

How to find first element in a sequence that matches a predicate in Python?

You can combine ifilter and islice to get just the first matching element.

>>> list(itertools.islice(itertools.ifilter(lambda n: n % 2 == 0, lst), 1))
[8]

However, I wouldn't consider this anyhow more readable or nicer than the original code you posted. Wrapped in a function it will be much nicer though. And since next only returns one element there is no need for islice anymore:

def find(pred, iterable):
    return next(itertools.ifilter(pred, iterable), None)

It returns None if no element was found.

However, you still have the rather slow call of the predicate function every loop. Please consider using a list comprehension or generator expression instead:

>>> next((x for x in lst if x % 2 == 0), None)
8

Is there a way to find the first element to match a Predicate?

It does exactly what you want. It doesn't run over all the elements. The filter method creates a stream and on top of it findFirst creates another stream.

So when you try to get the element of the stream that was created after findFirst() you'll get only the first one that matches the predicate.

Best way to check that is to add a print line or something like that inside the predicate.

Create a stream of integers for example from 0 to 10 and create a predicate that prints the number and then checks if it's divided by 3. You'll get this printed out: 0, 1, 2, 3 and that's it.

I wrote a question + answer in the past to explain in more details how it works: Understanding java 8 stream's filter method

Swift function to find first element of collection matching a predicate?

No there isn't, but you can write one yourself like this:

extension SequenceType {
    func first(@noescape pred: Generator.Element throws -> Bool) rethrows -> Generator.Element? {
        return try filter(pred).first
    }
}

EDIT: This version isn't optimal, since the filter creates a whole new array, even though only the first element would be needed. As noted by Martin R, lazy.filter also doesn't work for. This would be necessary to make it work with lazy:

extension CollectionType {
    func first(pred: Generator.Element -> Bool) -> Generator.Element? {
        return lazy.filter(pred).first
    }
}

Because:

• @noescape can't be used because @noescape means that the closure cannot escape the current function, which would be possible when passing it to the lazy filter (doesn't evaluate elements until it is asked to -> has to escape the predicate)
• throws can't be used because the filter is lazy -> errors wouldn't be thrown immediately, but rather when it is used the first time which would be when calling first, but first can't be throwing because it's a property. There are some discussions on making getters (and subscripts) throwing in future versions of Swift.
• CollectionType has to be used, because only LazyCollectionType has the first property.

So to really make it lazy and have all the @noescape, throws and SequenceType, you'd have to use an imperative approach:

extension SequenceType {
    func first(@noescape pred: Generator.Element throws -> Bool) rethrows -> Generator.Element? {
        for elem in self where try pred(elem) {
            return elem
        }
        return nil
    }
}

Get the first item from an iterable that matches a condition

Python 2.6+ and Python 3:

If you want StopIteration to be raised if no matching element is found:

next(x for x in the_iterable if x > 3)

If you want default_value (e.g. None) to be returned instead:

next((x for x in the_iterable if x > 3), default_value)

Note that you need an extra pair of parentheses around the generator expression in this case − they are needed whenever the generator expression isn't the only argument.

I see most answers resolutely ignore the next built-in and so I assume that for some mysterious reason they're 100% focused on versions 2.5 and older -- without mentioning the Python-version issue (but then I don't see that mention in the answers that do mention the next built-in, which is why I thought it necessary to provide an answer myself -- at least the "correct version" issue gets on record this way;-).

Python <= 2.5

The .next() method of iterators immediately raises StopIteration if the iterator immediately finishes -- i.e., for your use case, if no item in the iterable satisfies the condition. If you don't care (i.e., you know there must be at least one satisfactory item) then just use .next() (best on a genexp, line for the next built-in in Python 2.6 and better).

If you do care, wrapping things in a function as you had first indicated in your Q seems best, and while the function implementation you proposed is just fine, you could alternatively use itertools, a for...: break loop, or a genexp, or a try/except StopIteration as the function's body, as various answers suggested. There's not much added value in any of these alternatives so I'd go for the starkly-simple version you first proposed.

Find the first element that satisfies condition X in a Seq

If you're confident at least one will format will succeed:

formats.view.map{format => Try(format.parse(str)).toOption}.filter(_.isDefined).head

If you want to be a bit safer:

formats.view.map{format => Try(format.parse(str)).toOption}.find(_.isDefined)

Try was introduced in Scala 2.10.

A view is a type of collection that computes values lazily. It will apply the code within the Try to only as many items in the collection as is necessary to find the first one that is defined. If the first format applies to the string, then it won't try to apply the remaining formats to the string.

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

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.

Use Functor / Predicate to find the first element smaller than its predecessor in vector

You can use std::adjacent_find() for that.

auto iter = std::adjacent_find(begin(v), end(v), [](const auto& a, const auto& b) { return a < b; });

select first item of a collection that satisfies given predicate in clojure

There are multiple possibilities.

some

some returns the first non-nil value its predicate returns.

(some #(when (> % 10) %) (range)) ;; => 11

filter + first

filter retains those elements that match a predicate, first retrieves the first of them.

(first (filter #(> % 10) (range))) ;; => 11

remove + first

If you want to find the first element that does not match your predicate, remove is your friend:

(first (remove #(<= % 10) (range))) ;; => 11

Or with some:

(some #(when-not (<= % 10) %) (range)) ;; => 11

So, that's it, I guess.

Find first sequence item that matches a criterion

If you don't have any other indexes or sorted information for your objects, then you will have to iterate until such an object is found:

next(obj for obj in objs if obj.val == 5)

This is however faster than a complete list comprehension. Compare these two:

[i for i in xrange(100000) if i == 1000][0]

next(i for i in xrange(100000) if i == 1000)

The first one needs 5.75ms, the second one 58.3µs (100 times faster because the loop 100 times shorter).

---

Related Topics