From 9790e70150c83693fa2bcdc65814d01536bf4915 Mon Sep 17 00:00:00 2001 From: Silvan Mosberger Date: Wed, 31 May 2023 22:53:50 +0200 Subject: lib.list.findFirst: Make lazier There's no need to evaluate list elements after a matching element --- lib/lists.nix | 34 ++++++++++++++++++++++++++++++++-- 1 file changed, 32 insertions(+), 2 deletions(-) (limited to 'lib/lists.nix') diff --git a/lib/lists.nix b/lib/lists.nix index 2186cd4a79f60..5d9af0cf7114e 100644 --- a/lib/lists.nix +++ b/lib/lists.nix @@ -198,8 +198,38 @@ rec { default: # Input list list: - let found = filter pred list; - in if found == [] then default else head found; + 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 + elemAt list resultIndex; /* Return true if function `pred` returns true for at least one element of `list`. -- cgit 1.4.1