findFirstIndex
lib.lists.findFirstIndex
Docs pulled from | This Revision | 16 minutes ago
Find the first index in the list matching the specified
predicate or return default
if no such element exists.
Inputs
pred
-
Predicate
default
-
Default value to return
list
-
Input list
Type
findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b)
Examples
lib.lists.findFirstIndex
usage example
findFirstIndex (x: x > 3) null [ 0 6 4 ]
=> 1
findFirstIndex (x: x > 9) null [ 0 6 4 ]
=> null
Noogle detected
Implementation
The following is the current implementation of this function.
findFirstIndex =
pred: default: list:
let
# A naive recursive implementation would be much simpler, but
# would also overflow the evaluator stack. We use `foldl'` as a workaround
# because it reuses the same stack space, evaluating the function for one
# element after another. We can't return early, so this means that we
# sacrifice early cutoff, but that appears to be an acceptable cost. A
# clever scheme with "exponential search" is possible, but appears over-
# engineered for now. See https://github.com/NixOS/nixpkgs/pull/235267
# Invariant:
# - if index < 0 then el == elemAt list (- index - 1) and all elements before el didn't satisfy pred
# - if index >= 0 then pred (elemAt list index) and all elements before (elemAt list index) didn't satisfy pred
#
# We start with index -1 and the 0'th element of the list, which satisfies the invariant
resultIndex = foldl' (
index: el:
if index < 0 then
# No match yet before the current index, we need to check the element
if pred el then
# We have a match! Turn it into the actual index to prevent future iterations from modifying it
-index - 1
else
# Still no match, update the index to the next element (we're counting down, so minus one)
index - 1
else
# There's already a match, propagate the index without evaluating anything
index
) (-1) list;
in
if resultIndex < 0 then default else resultIndex;