diff options
-rw-r--r-- | lib/lists.nix | 70 | ||||
-rw-r--r-- | lib/tests/misc.nix | 83 |
2 files changed, 124 insertions, 29 deletions
diff --git a/lib/lists.nix b/lib/lists.nix index 5d9af0cf7114e..3e058b3f1aef1 100644 --- a/lib/lists.nix +++ b/lib/lists.nix @@ -3,7 +3,7 @@ { lib }: let inherit (lib.strings) toInt; - inherit (lib.trivial) compare min; + inherit (lib.trivial) compare min id; inherit (lib.attrsets) mapAttrs; in rec { @@ -180,18 +180,18 @@ rec { else if len != 1 then multiple else head found; - /* Find the first element in the list matching the specified + /* Find the first index in the list matching the specified predicate or return `default` if no such element exists. - Type: findFirst :: (a -> bool) -> a -> [a] -> a + Type: findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b) Example: - findFirst (x: x > 3) 7 [ 1 6 4 ] - => 6 - findFirst (x: x > 9) 7 [ 1 6 4 ] - => 7 + findFirstIndex (x: x > 3) null [ 0 6 4 ] + => 1 + findFirstIndex (x: x > 9) null [ 0 6 4 ] + => null */ - findFirst = + findFirstIndex = # Predicate pred: # Default value to return @@ -229,7 +229,33 @@ rec { if resultIndex < 0 then default else - elemAt list resultIndex; + resultIndex; + + /* Find the first element in the list matching the specified + predicate or return `default` if no such element exists. + + Type: findFirst :: (a -> bool) -> a -> [a] -> a + + Example: + findFirst (x: x > 3) 7 [ 1 6 4 ] + => 6 + findFirst (x: x > 9) 7 [ 1 6 4 ] + => 7 + */ + findFirst = + # Predicate + pred: + # Default value to return + default: + # Input list + list: + let + index = findFirstIndex pred null list; + in + if index == null then + default + else + elemAt list index; /* Return true if function `pred` returns true for at least one element of `list`. @@ -637,6 +663,32 @@ rec { else if start + count > len then len - start else count); + /* The common prefix of two lists. + + Type: commonPrefix :: [a] -> [a] -> [a] + + Example: + commonPrefix [ 1 2 3 4 5 6 ] [ 1 2 4 8 ] + => [ 1 2 ] + commonPrefix [ 1 2 3 ] [ 1 2 3 4 5 ] + => [ 1 2 3 ] + commonPrefix [ 1 2 3 ] [ 4 5 6 ] + => [ ] + */ + commonPrefix = + list1: + list2: + let + # Zip the lists together into a list of booleans whether each element matches + matchings = zipListsWith (fst: snd: fst != snd) list1 list2; + # Find the first index where the elements don't match, + # which will then also be the length of the common prefix. + # If all elements match, we fall back to the length of the zipped list, + # which is the same as the length of the smaller list. + commonPrefixLength = findFirstIndex id (length matchings) matchings; + in + take commonPrefixLength list1; + /* Return the last element of a list. This function throws an error if the list is empty. diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix index 56bf31ea5da61..887ea39a080df 100644 --- a/lib/tests/misc.nix +++ b/lib/tests/misc.nix @@ -500,6 +500,39 @@ runTests { expected = { a = [ 2 3 ]; b = [7]; c = [8];}; }; + testListCommonPrefixExample1 = { + expr = lists.commonPrefix [ 1 2 3 4 5 6 ] [ 1 2 4 8 ]; + expected = [ 1 2 ]; + }; + testListCommonPrefixExample2 = { + expr = lists.commonPrefix [ 1 2 3 ] [ 1 2 3 4 5 ]; + expected = [ 1 2 3 ]; + }; + testListCommonPrefixExample3 = { + expr = lists.commonPrefix [ 1 2 3 ] [ 4 5 6 ]; + expected = [ ]; + }; + testListCommonPrefixEmpty = { + expr = lists.commonPrefix [ ] [ 1 2 3 ]; + expected = [ ]; + }; + testListCommonPrefixSame = { + expr = lists.commonPrefix [ 1 2 3 ] [ 1 2 3 ]; + expected = [ 1 2 3 ]; + }; + testListCommonPrefixLazy = { + expr = lists.commonPrefix [ 1 ] [ 1 (abort "lib.lists.commonPrefix shouldn't evaluate this")]; + expected = [ 1 ]; + }; + # This would stack overflow if `commonPrefix` were implemented using recursion + testListCommonPrefixLong = + let + longList = genList (n: n) 100000; + in { + expr = lists.commonPrefix longList longList; + expected = longList; + }; + testSort = { expr = sort builtins.lessThan [ 40 2 30 42 ]; expected = [2 30 40 42]; @@ -530,45 +563,55 @@ runTests { expected = false; }; - testFindFirstExample1 = { - expr = findFirst (x: x > 3) 7 [ 1 6 4 ]; - expected = 6; + testFindFirstIndexExample1 = { + expr = lists.findFirstIndex (x: x > 3) (abort "index found, so a default must not be evaluated") [ 1 6 4 ]; + expected = 1; }; - testFindFirstExample2 = { - expr = findFirst (x: x > 9) 7 [ 1 6 4 ]; - expected = 7; + testFindFirstIndexExample2 = { + expr = lists.findFirstIndex (x: x > 9) "a very specific default" [ 1 6 4 ]; + expected = "a very specific default"; }; - testFindFirstEmpty = { - expr = findFirst (abort "when the list is empty, the predicate is not needed") null []; + testFindFirstIndexEmpty = { + expr = lists.findFirstIndex (abort "when the list is empty, the predicate is not needed") null []; expected = null; }; - testFindFirstSingleMatch = { - expr = findFirst (x: x == 5) null [ 5 ]; - expected = 5; + testFindFirstIndexSingleMatch = { + expr = lists.findFirstIndex (x: x == 5) null [ 5 ]; + expected = 0; }; - testFindFirstSingleDefault = { - expr = findFirst (x: false) null [ (abort "if the predicate doesn't access the value, it must not be evaluated") ]; + testFindFirstIndexSingleDefault = { + expr = lists.findFirstIndex (x: false) null [ (abort "if the predicate doesn't access the value, it must not be evaluated") ]; expected = null; }; - testFindFirstNone = { - expr = builtins.tryEval (findFirst (x: x == 2) null [ 1 (throw "the last element must be evaluated when there's no match") ]); + testFindFirstIndexNone = { + expr = builtins.tryEval (lists.findFirstIndex (x: x == 2) null [ 1 (throw "the last element must be evaluated when there's no match") ]); expected = { success = false; value = false; }; }; # Makes sure that the implementation doesn't cause a stack overflow - testFindFirstBig = { - expr = findFirst (x: x == 1000000) null (range 0 1000000); + testFindFirstIndexBig = { + expr = lists.findFirstIndex (x: x == 1000000) null (range 0 1000000); expected = 1000000; }; - testFindFirstLazy = { - expr = findFirst (x: x == 1) 7 [ 1 (abort "list elements after the match must not be evaluated") ]; - expected = 1; + testFindFirstIndexLazy = { + expr = lists.findFirstIndex (x: x == 1) null [ 1 (abort "list elements after the match must not be evaluated") ]; + expected = 0; + }; + + testFindFirstExample1 = { + expr = lists.findFirst (x: x > 3) 7 [ 1 6 4 ]; + expected = 6; + }; + + testFindFirstExample2 = { + expr = lists.findFirst (x: x > 9) 7 [ 1 6 4 ]; + expected = 7; }; # ATTRSETS |