First matching element in collection

General Usage
1

Sometimes I want to find the first element in a collection that satisfies some predicate f. The collection may not be (O(1)) indexable, so findfirst then lookup is not ideal.

I am looking for something like

function firstmatching(f, itr)
    state = ()
    while true
        y = iterate(itr, state...)
        y ≡ nothing && return nothing
        elt = first(y)
        f(elt) && return Some(elt)
        state = Base.tail(y)
    end
end

Eg

julia> firstmatching(isodd, (2, 4, 5))
Some(5)

julia> firstmatching(x -> last(x) ≡ :a, [1 => :b, 2 => :c, 3 => :a])
Some(3 => :a)

Does something similar exist in Base, or a commonly used package?

2

How about first(Iterators.filter(f, itr))?

3

I thought about that too, but besides being kind of complicated,

julia> first(Iterators.filter(isodd, 2:2:10))
ERROR: ArgumentError: collection must be non-empty
Stacktrace:
 [1] first(::Base.Iterators.Filter{typeof(isodd),StepRange{Int64,Int64}}) at ./abstractarray.jl:289
 [2] top-level scope at none:0
4

Complicated? I feel like this is precisely the kind of thing Iterators.filter was made for. To support nothing, you could do:

function firstmatching2(f, itr)
    it = iterate(Iterators.filter(f, itr))
    it ≡ nothing ? nothing : it[1]
end

The advantage of reusing existing code is that you get maintenance, testing and (usually) a decent quality implementation for free. For example:

julia> A = [0:2:1000000; 1];

julia> @btime firstmatching(isodd, A)
  34.428 ms (1999497 allocations: 38.14 MiB)
Some(1)

julia> @btime firstmatching2(isodd, A)
  334.707 μs (2 allocations: 48 bytes)
1

I’m sure you can fix this in your implementation (if it matters to you), but if you reuse existing code, you don’t have to worry about these things.

1 Like