diff options
author | Silvan Mosberger <silvan.mosberger@tweag.io> | 2023-05-31 22:53:50 +0200 |
---|---|---|
committer | Silvan Mosberger <silvan.mosberger@tweag.io> | 2023-06-06 17:17:32 +0200 |
commit | 9790e70150c83693fa2bcdc65814d01536bf4915 (patch) | |
tree | 2835982e4941df3c2e78573eb7e64302feb64cac /lib/lists.nix | |
parent | 6996f76885d81fbc1b066fe346713630e6ac9e1b (diff) |
lib.list.findFirst: Make lazier
There's no need to evaluate list elements after a matching element
Diffstat (limited to 'lib/lists.nix')
-rw-r--r-- | lib/lists.nix | 34 |
1 files changed, 32 insertions, 2 deletions
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`. |