findFirstIndex
lib.lists.findFirstIndex
Docs pulled from  This Revision  8 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;