diff options
Diffstat (limited to 'nixpkgs/lib/lists.nix')
| -rw-r--r-- | nixpkgs/lib/lists.nix | 1704 |
1 files changed, 1331 insertions, 373 deletions
diff --git a/nixpkgs/lib/lists.nix b/nixpkgs/lib/lists.nix index 05216c1a66eb..c162f921280d 100644 --- a/nixpkgs/lib/lists.nix +++ b/nixpkgs/lib/lists.nix @@ -1,4 +1,6 @@ -/* General list operations. */ +/** + General list operations. +*/ { lib }: let inherit (lib.strings) toInt; @@ -9,45 +11,112 @@ rec { inherit (builtins) head tail length isList elemAt concatLists filter elem genList map; - /* Create a list consisting of a single element. `singleton x` is - sometimes more convenient with respect to indentation than `[x]` - when x spans multiple lines. + /** + Create a list consisting of a single element. `singleton x` is + sometimes more convenient with respect to indentation than `[x]` + when x spans multiple lines. - Type: singleton :: a -> [a] + # Inputs - Example: - singleton "foo" - => [ "foo" ] + `x` + + : 1\. Function argument + + # Type + + ``` + singleton :: a -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.singleton` usage example + + ```nix + singleton "foo" + => [ "foo" ] + ``` + + ::: */ singleton = x: [x]; - /* Apply the function to each element in the list. Same as `map`, but arguments - flipped. + /** + Apply the function to each element in the list. + Same as `map`, but arguments flipped. + + # Inputs + + `xs` + + : 1\. Function argument + + `f` + + : 2\. Function argument + + # Type + + ``` + forEach :: [a] -> (a -> b) -> [b] + ``` + + # Examples + :::{.example} + ## `lib.lists.forEach` usage example - Type: forEach :: [a] -> (a -> b) -> [b] + ```nix + forEach [ 1 2 ] (x: + toString x + ) + => [ "1" "2" ] + ``` - Example: - forEach [ 1 2 ] (x: - toString x - ) - => [ "1" "2" ] + ::: */ forEach = xs: f: map f xs; - /* “right fold” a binary function `op` between successive elements of - `list` with `nul` as the starting value, i.e., - `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))`. + /** + “right fold” a binary function `op` between successive elements of + `list` with `nul` as the starting value, i.e., + `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))`. + + + # Inputs + + `op` + + : 1\. Function argument + + `nul` - Type: foldr :: (a -> b -> b) -> b -> [a] -> b + : 2\. Function argument - Example: - concat = foldr (a: b: a + b) "z" - concat [ "a" "b" "c" ] - => "abcz" - # different types - strange = foldr (int: str: toString (int + 1) + str) "a" - strange [ 1 2 3 4 ] - => "2345a" + `list` + + : 3\. Function argument + + # Type + + ``` + foldr :: (a -> b -> b) -> b -> [a] -> b + ``` + + # Examples + :::{.example} + ## `lib.lists.foldr` usage example + + ```nix + concat = foldr (a: b: a + b) "z" + concat [ "a" "b" "c" ] + => "abcz" + # different types + strange = foldr (int: str: toString (int + 1) + str) "a" + strange [ 1 2 3 4 ] + => "2345a" + ``` + + ::: */ foldr = op: nul: list: let @@ -58,24 +127,53 @@ rec { else op (elemAt list n) (fold' (n + 1)); in fold' 0; - /* `fold` is an alias of `foldr` for historic reasons */ + /** + `fold` is an alias of `foldr` for historic reasons + */ # FIXME(Profpatsch): deprecate? fold = foldr; - /* “left fold”, like `foldr`, but from the left: - `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`. + /** + “left fold”, like `foldr`, but from the left: + + `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`. + + # Inputs + + `op` + + : 1\. Function argument + + `nul` + + : 2\. Function argument + + `list` - Type: foldl :: (b -> a -> b) -> b -> [a] -> b + : 3\. Function argument - Example: - lconcat = foldl (a: b: a + b) "z" - lconcat [ "a" "b" "c" ] - => "zabc" - # different types - lstrange = foldl (str: int: str + toString (int + 1)) "a" - lstrange [ 1 2 3 4 ] - => "a2345" + # Type + + ``` + foldl :: (b -> a -> b) -> b -> [a] -> b + ``` + + # Examples + :::{.example} + ## `lib.lists.foldl` usage example + + ```nix + lconcat = foldl (a: b: a + b) "z" + lconcat [ "a" "b" "c" ] + => "zabc" + # different types + lstrange = foldl (str: int: str + toString (int + 1)) "a" + lstrange [ 1 2 3 4 ] + => "a2345" + ``` + + ::: */ foldl = op: nul: list: let @@ -85,7 +183,7 @@ rec { else op (foldl' (n - 1)) (elemAt list n); in foldl' (length list - 1); - /* + /** Reduce a list by applying a binary operator from left to right, starting with an initial accumulator. @@ -119,131 +217,305 @@ rec { op (op (... (op (op (op acc₀ x₀) x₁) x₂) ...) xₙ₋₁) xₙ ``` - Type: foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc + # Inputs - Example: - foldl' (acc: x: acc + x) 0 [1 2 3] - => 6 - */ - foldl' = - /* The binary operation to run, where the two arguments are: + `op` + + : The binary operation to run, where the two arguments are: 1. `acc`: The current accumulator value: Either the initial one for the first iteration, or the result of the previous iteration 2. `x`: The corresponding list element for this iteration - */ + + `acc` + + : The initial accumulator value. + + The accumulator value is evaluated in any case before the first iteration starts. + + To avoid evaluation even before the `list` argument is given an eta expansion can be used: + + ```nix + list: lib.foldl' op acc list + ``` + + `list` + + : The list to fold + + # Type + + ``` + foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc + ``` + + # Examples + :::{.example} + ## `lib.lists.foldl'` usage example + + ```nix + foldl' (acc: x: acc + x) 0 [1 2 3] + => 6 + ``` + + ::: + */ + foldl' = op: - # The initial accumulator value acc: - # The list to fold - list: - # The builtin `foldl'` is a bit lazier than one might expect. # See https://github.com/NixOS/nix/pull/7158. # In particular, the initial accumulator value is not forced before the first iteration starts. builtins.seq acc - (builtins.foldl' op acc list); + (builtins.foldl' op acc); + + /** + Map with index starting from 0 + + # Inputs + + `f` + + : 1\. Function argument - /* Map with index starting from 0 + `list` - Type: imap0 :: (int -> a -> b) -> [a] -> [b] + : 2\. Function argument - Example: - imap0 (i: v: "${v}-${toString i}") ["a" "b"] - => [ "a-0" "b-1" ] + # Type + + ``` + imap0 :: (int -> a -> b) -> [a] -> [b] + ``` + + # Examples + :::{.example} + ## `lib.lists.imap0` usage example + + ```nix + imap0 (i: v: "${v}-${toString i}") ["a" "b"] + => [ "a-0" "b-1" ] + ``` + + ::: */ imap0 = f: list: genList (n: f n (elemAt list n)) (length list); - /* Map with index starting from 1 + /** + Map with index starting from 1 + - Type: imap1 :: (int -> a -> b) -> [a] -> [b] + # Inputs - Example: - imap1 (i: v: "${v}-${toString i}") ["a" "b"] - => [ "a-1" "b-2" ] + `f` + + : 1\. Function argument + + `list` + + : 2\. Function argument + + # Type + + ``` + imap1 :: (int -> a -> b) -> [a] -> [b] + ``` + + # Examples + :::{.example} + ## `lib.lists.imap1` usage example + + ```nix + imap1 (i: v: "${v}-${toString i}") ["a" "b"] + => [ "a-1" "b-2" ] + ``` + + ::: */ imap1 = f: list: genList (n: f (n + 1) (elemAt list n)) (length list); - /* Map and concatenate the result. + /** + Map and concatenate the result. + + # Type + + ``` + concatMap :: (a -> [b]) -> [a] -> [b] + ``` + + # Examples + :::{.example} + ## `lib.lists.concatMap` usage example - Type: concatMap :: (a -> [b]) -> [a] -> [b] + ```nix + concatMap (x: [x] ++ ["z"]) ["a" "b"] + => [ "a" "z" "b" "z" ] + ``` - Example: - concatMap (x: [x] ++ ["z"]) ["a" "b"] - => [ "a" "z" "b" "z" ] + ::: */ concatMap = builtins.concatMap; - /* Flatten the argument into a single list; that is, nested lists are - spliced into the top-level lists. + /** + Flatten the argument into a single list; that is, nested lists are + spliced into the top-level lists. + + + # Inputs + + `x` + + : 1\. Function argument + + + # Examples + :::{.example} + ## `lib.lists.flatten` usage example + + ```nix + flatten [1 [2 [3] 4] 5] + => [1 2 3 4 5] + flatten 1 + => [1] + ``` - Example: - flatten [1 [2 [3] 4] 5] - => [1 2 3 4 5] - flatten 1 - => [1] + ::: */ flatten = x: if isList x then concatMap (y: flatten y) x else [x]; - /* Remove elements equal to 'e' from a list. Useful for buildInputs. + /** + Remove elements equal to 'e' from a list. Useful for buildInputs. + + + # Inputs + + `e` - Type: remove :: a -> [a] -> [a] + : Element to remove from `list` - Example: - remove 3 [ 1 3 4 3 ] - => [ 1 4 ] + `list` + + : The list + + # Type + + ``` + remove :: a -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.remove` usage example + + ```nix + remove 3 [ 1 3 4 3 ] + => [ 1 4 ] + ``` + + ::: */ remove = - # Element to remove from the list e: filter (x: x != e); - /* Find the sole element in the list matching the specified - predicate, returns `default` if no such element exists, or - `multiple` if there are multiple matching elements. + /** + Find the sole element in the list matching the specified + predicate. + + Returns `default` if no such element exists, or + `multiple` if there are multiple matching elements. + + + # Inputs + + `pred` + + : Predicate + + `default` + + : Default value to return if element was not found. + + `multiple` + + : Default value to return if more than one element was found + + `list` + + : Input list - Type: findSingle :: (a -> bool) -> a -> a -> [a] -> a + # Type - Example: - findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ] - => "multiple" - findSingle (x: x == 3) "none" "multiple" [ 1 3 ] - => 3 - findSingle (x: x == 3) "none" "multiple" [ 1 9 ] - => "none" + ``` + findSingle :: (a -> bool) -> a -> a -> [a] -> a + ``` + + # Examples + :::{.example} + ## `lib.lists.findSingle` usage example + + ```nix + findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ] + => "multiple" + findSingle (x: x == 3) "none" "multiple" [ 1 3 ] + => 3 + findSingle (x: x == 3) "none" "multiple" [ 1 9 ] + => "none" + ``` + + ::: */ findSingle = - # Predicate pred: - # Default value to return if element was not found. default: - # Default value to return if more than one element was found multiple: - # Input list list: let found = filter pred list; len = length found; in if len == 0 then default else if len != 1 then multiple else head found; - /* Find the first index in the list matching the specified - predicate or return `default` if no such element exists. + /** + 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) + ``` - Type: findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b) + # Examples + :::{.example} + ## `lib.lists.findFirstIndex` usage example - Example: - findFirstIndex (x: x > 3) null [ 0 6 4 ] - => 1 - findFirstIndex (x: x > 9) null [ 0 6 4 ] - => null + ```nix + findFirstIndex (x: x > 3) null [ 0 6 4 ] + => 1 + findFirstIndex (x: x > 9) null [ 0 6 4 ] + => null + ``` + + ::: */ findFirstIndex = - # Predicate pred: - # Default value to return default: - # Input list list: let # A naive recursive implementation would be much simpler, but @@ -278,23 +550,46 @@ rec { else resultIndex; - /* Find the first element in the list matching the specified - predicate or return `default` if no such element exists. + /** + Find the first element in the list matching the specified + predicate or return `default` if no such element exists. + + # Inputs + + `pred` + + : Predicate + + `default` + + : Default value to return + + `list` - Type: findFirst :: (a -> bool) -> a -> [a] -> a + : Input list + + # Type + + ``` + findFirst :: (a -> bool) -> a -> [a] -> a + ``` + + # Examples + :::{.example} + ## `lib.lists.findFirst` usage example + + ```nix + findFirst (x: x > 3) 7 [ 1 6 4 ] + => 6 + findFirst (x: x > 9) 7 [ 1 6 4 ] + => 7 + ``` - 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; @@ -304,152 +599,359 @@ rec { else elemAt list index; - /* Return true if function `pred` returns true for at least one - element of `list`. + /** + Return true if function `pred` returns true for at least one + element of `list`. - Type: any :: (a -> bool) -> [a] -> bool + # Inputs - Example: - any isString [ 1 "a" { } ] - => true - any isString [ 1 { } ] - => false + `pred` + + : Predicate + + `list` + + : Input list + + # Type + + ``` + any :: (a -> bool) -> [a] -> bool + ``` + + # Examples + :::{.example} + ## `lib.lists.any` usage example + + ```nix + any isString [ 1 "a" { } ] + => true + any isString [ 1 { } ] + => false + ``` + + ::: */ any = builtins.any; - /* Return true if function `pred` returns true for all elements of - `list`. + /** + Return true if function `pred` returns true for all elements of + `list`. + + # Inputs + + `pred` + + : Predicate + + `list` - Type: all :: (a -> bool) -> [a] -> bool + : Input list - Example: - all (x: x < 3) [ 1 2 ] - => true - all (x: x < 3) [ 1 2 3 ] - => false + # Type + + ``` + all :: (a -> bool) -> [a] -> bool + ``` + + # Examples + :::{.example} + ## `lib.lists.all` usage example + + ```nix + all (x: x < 3) [ 1 2 ] + => true + all (x: x < 3) [ 1 2 3 ] + => false + ``` + + ::: */ all = builtins.all; - /* Count how many elements of `list` match the supplied predicate - function. + /** + Count how many elements of `list` match the supplied predicate + function. + + # Inputs + + `pred` + + : Predicate + + # Type + + ``` + count :: (a -> bool) -> [a] -> int + ``` + + # Examples + :::{.example} + ## `lib.lists.count` usage example - Type: count :: (a -> bool) -> [a] -> int + ```nix + count (x: x == 3) [ 3 2 3 4 6 ] + => 2 + ``` - Example: - count (x: x == 3) [ 3 2 3 4 6 ] - => 2 + ::: */ count = - # Predicate pred: foldl' (c: x: if pred x then c + 1 else c) 0; - /* Return a singleton list or an empty list, depending on a boolean - value. Useful when building lists with optional elements - (e.g. `++ optional (system == "i686-linux") firefox`). + /** + Return a singleton list or an empty list, depending on a boolean + value. Useful when building lists with optional elements + (e.g. `++ optional (system == "i686-linux") firefox`). + + # Inputs + + `cond` + + : 1\. Function argument + + `elem` + + : 2\. Function argument + + # Type - Type: optional :: bool -> a -> [a] + ``` + optional :: bool -> a -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.optional` usage example - Example: - optional true "foo" - => [ "foo" ] - optional false "foo" - => [ ] + ```nix + optional true "foo" + => [ "foo" ] + optional false "foo" + => [ ] + ``` + + ::: */ optional = cond: elem: if cond then [elem] else []; - /* Return a list or an empty list, depending on a boolean value. + /** + Return a list or an empty list, depending on a boolean value. + + # Inputs + + `cond` - Type: optionals :: bool -> [a] -> [a] + : Condition - Example: - optionals true [ 2 3 ] - => [ 2 3 ] - optionals false [ 2 3 ] - => [ ] + `elems` + + : List to return if condition is true + + # Type + + ``` + optionals :: bool -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.optionals` usage example + + ```nix + optionals true [ 2 3 ] + => [ 2 3 ] + optionals false [ 2 3 ] + => [ ] + ``` + + ::: */ optionals = - # Condition cond: - # List to return if condition is true elems: if cond then elems else []; - /* If argument is a list, return it; else, wrap it in a singleton - list. If you're using this, you should almost certainly - reconsider if there isn't a more "well-typed" approach. + /** + If argument is a list, return it; else, wrap it in a singleton + list. If you're using this, you should almost certainly + reconsider if there isn't a more "well-typed" approach. + + # Inputs + + `x` + + : 1\. Function argument + + # Examples + :::{.example} + ## `lib.lists.toList` usage example + + ```nix + toList [ 1 2 ] + => [ 1 2 ] + toList "hi" + => [ "hi "] + ``` - Example: - toList [ 1 2 ] - => [ 1 2 ] - toList "hi" - => [ "hi "] + ::: */ toList = x: if isList x then x else [x]; - /* Return a list of integers from `first` up to and including `last`. + /** + Return a list of integers from `first` up to and including `last`. + + # Inputs + + `first` + + : First integer in the range + + `last` + + : Last integer in the range + + # Type + + ``` + range :: int -> int -> [int] + ``` - Type: range :: int -> int -> [int] + # Examples + :::{.example} + ## `lib.lists.range` usage example - Example: - range 2 4 - => [ 2 3 4 ] - range 3 2 - => [ ] + ```nix + range 2 4 + => [ 2 3 4 ] + range 3 2 + => [ ] + ``` + + ::: */ range = - # First integer in the range first: - # Last integer in the range last: if first > last then [] else genList (n: first + n) (last - first + 1); - /* Return a list with `n` copies of an element. + /** + Return a list with `n` copies of an element. + + # Inputs + + `n` + + : 1\. Function argument - Type: replicate :: int -> a -> [a] + `elem` - Example: - replicate 3 "a" - => [ "a" "a" "a" ] - replicate 2 true - => [ true true ] + : 2\. Function argument + + # Type + + ``` + replicate :: int -> a -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.replicate` usage example + + ```nix + replicate 3 "a" + => [ "a" "a" "a" ] + replicate 2 true + => [ true true ] + ``` + + ::: */ replicate = n: elem: genList (_: elem) n; - /* Splits the elements of a list in two lists, `right` and - `wrong`, depending on the evaluation of a predicate. + /** + Splits the elements of a list in two lists, `right` and + `wrong`, depending on the evaluation of a predicate. + + # Inputs + + `pred` + + : Predicate + + `list` + + : Input list + + # Type + + ``` + (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; } + ``` + + # Examples + :::{.example} + ## `lib.lists.partition` usage example - Type: (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; } + ```nix + partition (x: x > 2) [ 5 1 2 3 4 ] + => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; } + ``` - Example: - partition (x: x > 2) [ 5 1 2 3 4 ] - => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; } + ::: */ partition = builtins.partition; - /* Splits the elements of a list into many lists, using the return value of a predicate. - Predicate should return a string which becomes keys of attrset `groupBy` returns. + /** + Splits the elements of a list into many lists, using the return value of a predicate. + Predicate should return a string which becomes keys of attrset `groupBy` returns. + `groupBy'` allows to customise the combining function and initial value + + # Inputs + + `op` + + : 1\. Function argument + + `nul` + + : 2\. Function argument - `groupBy'` allows to customise the combining function and initial value + `pred` - Example: - groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ] - => { true = [ 5 3 4 ]; false = [ 1 2 ]; } - groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";} - {name = "xfce"; script = "xfce4-session &";} - {name = "icewm"; script = "icewmbg &";} - {name = "mate"; script = "gnome-session &";} - ] - => { icewm = [ { name = "icewm"; script = "icewm &"; } - { name = "icewm"; script = "icewmbg &"; } ]; - mate = [ { name = "mate"; script = "gnome-session &"; } ]; - xfce = [ { name = "xfce"; script = "xfce4-session &"; } ]; - } + : 3\. Function argument - groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ] - => { true = 12; false = 3; } + `lst` + + : 4\. Function argument + + + # Examples + :::{.example} + ## `lib.lists.groupBy'` usage example + + ```nix + groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ] + => { true = [ 5 3 4 ]; false = [ 1 2 ]; } + groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";} + {name = "xfce"; script = "xfce4-session &";} + {name = "icewm"; script = "icewmbg &";} + {name = "mate"; script = "gnome-session &";} + ] + => { icewm = [ { name = "icewm"; script = "icewm &"; } + { name = "icewm"; script = "icewmbg &"; } ]; + mate = [ { name = "mate"; script = "gnome-session &"; } ]; + xfce = [ { name = "xfce"; script = "xfce4-session &"; } ]; + } + + groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ] + => { true = 12; false = 3; } + ``` + + ::: */ groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst); @@ -461,68 +963,153 @@ rec { r // { ${key} = (r.${key} or []) ++ [e]; } ) {}); - /* Merges two lists of the same size together. If the sizes aren't the same - the merging stops at the shortest. How both lists are merged is defined - by the first argument. + /** + Merges two lists of the same size together. If the sizes aren't the same + the merging stops at the shortest. How both lists are merged is defined + by the first argument. + + # Inputs + + `f` - Type: zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c] + : Function to zip elements of both lists - Example: - zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"] - => ["he" "lo"] + `fst` + + : First list + + `snd` + + : Second list + + # Type + + ``` + zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c] + ``` + + # Examples + :::{.example} + ## `lib.lists.zipListsWith` usage example + + ```nix + zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"] + => ["he" "lo"] + ``` + + ::: */ zipListsWith = - # Function to zip elements of both lists f: - # First list fst: - # Second list snd: genList (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd)); - /* Merges two lists of the same size together. If the sizes aren't the same - the merging stops at the shortest. + /** + Merges two lists of the same size together. If the sizes aren't the same + the merging stops at the shortest. + + # Inputs + + `fst` - Type: zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }] + : First list - Example: - zipLists [ 1 2 ] [ "a" "b" ] - => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ] + `snd` + + : Second list + + # Type + + ``` + zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }] + ``` + + # Examples + :::{.example} + ## `lib.lists.zipLists` usage example + + ```nix + zipLists [ 1 2 ] [ "a" "b" ] + => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ] + ``` + + ::: */ zipLists = zipListsWith (fst: snd: { inherit fst snd; }); - /* Reverse the order of the elements of a list. + /** + Reverse the order of the elements of a list. + + # Inputs + + `xs` + + : 1\. Function argument - Type: reverseList :: [a] -> [a] + # Type - Example: + ``` + reverseList :: [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.reverseList` usage example - reverseList [ "b" "o" "j" ] - => [ "j" "o" "b" ] + ```nix + reverseList [ "b" "o" "j" ] + => [ "j" "o" "b" ] + ``` + + ::: */ reverseList = xs: let l = length xs; in genList (n: elemAt xs (l - n - 1)) l; - /* Depth-First Search (DFS) for lists `list != []`. + /** + Depth-First Search (DFS) for lists `list != []`. + + `before a b == true` means that `b` depends on `a` (there's an + edge from `b` to `a`). + + + # Inputs - `before a b == true` means that `b` depends on `a` (there's an - edge from `b` to `a`). + `stopOnCycles` - Example: - listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ] - == { minimal = "/"; # minimal element - visited = [ "/home/user" ]; # seen elements (in reverse order) - rest = [ "/home" "other" ]; # everything else - } + : 1\. Function argument - listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ] - == { cycle = "/"; # cycle encountered at this element - loops = [ "/" ]; # and continues to these elements - visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order) - rest = [ "/home" "other" ]; # everything else + `before` - */ + : 2\. Function argument + + `list` + + : 3\. Function argument + + + # Examples + :::{.example} + ## `lib.lists.listDfs` usage example + + ```nix + listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ] + == { minimal = "/"; # minimal element + visited = [ "/home/user" ]; # seen elements (in reverse order) + rest = [ "/home" "other" ]; # everything else + } + + listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ] + == { cycle = "/"; # cycle encountered at this element + loops = [ "/" ]; # and continues to these elements + visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order) + rest = [ "/home" "other" ]; # everything else + ``` + + ::: + */ listDfs = stopOnCycles: before: list: let dfs' = us: visited: rest: @@ -540,28 +1127,46 @@ rec { (tail b.right ++ b.wrong); in dfs' (head list) [] (tail list); - /* Sort a list based on a partial ordering using DFS. This - implementation is O(N^2), if your ordering is linear, use `sort` - instead. + /** + Sort a list based on a partial ordering using DFS. This + implementation is O(N^2), if your ordering is linear, use `sort` + instead. - `before a b == true` means that `b` should be after `a` - in the result. + `before a b == true` means that `b` should be after `a` + in the result. - Example: - toposort hasPrefix [ "/home/user" "other" "/" "/home" ] - == { result = [ "/" "/home" "/home/user" "other" ]; } + # Inputs - toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ] - == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle - loops = [ "/" ]; } # loops back to these elements + `before` - toposort hasPrefix [ "other" "/home/user" "/home" "/" ] - == { result = [ "other" "/" "/home" "/home/user" ]; } + : 1\. Function argument - toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; } + `list` - */ + : 2\. Function argument + + + # Examples + :::{.example} + ## `lib.lists.toposort` usage example + + ```nix + toposort hasPrefix [ "/home/user" "other" "/" "/home" ] + == { result = [ "/" "/home" "/home/user" "other" ]; } + + toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ] + == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle + loops = [ "/" ]; } # loops back to these elements + + toposort hasPrefix [ "other" "/home/user" "/home" "/" ] + == { result = [ "other" "/" "/home" "/home/user" ]; } + + toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; } + ``` + + ::: + */ toposort = before: list: let dfsthis = listDfs true before list; @@ -581,24 +1186,45 @@ rec { else # there are no cycles { result = [ dfsthis.minimal ] ++ toporest.result; }; - /* Sort a list based on a comparator function which compares two - elements and returns true if the first argument is strictly below - the second argument. The returned list is sorted in an increasing - order. The implementation does a quick-sort. + /** + Sort a list based on a comparator function which compares two + elements and returns true if the first argument is strictly below + the second argument. The returned list is sorted in an increasing + order. The implementation does a quick-sort. + + See also [`sortOn`](#function-library-lib.lists.sortOn), which applies the + default comparison on a function-derived property, and may be more efficient. + + # Inputs + + `comparator` + + : 1\. Function argument + + `list` + + : 2\. Function argument + + # Type - See also [`sortOn`](#function-library-lib.lists.sortOn), which applies the - default comparison on a function-derived property, and may be more efficient. + ``` + sort :: (a -> a -> Bool) -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.sort` usage example - Example: - sort (p: q: p < q) [ 5 3 7 ] - => [ 3 5 7 ] + ```nix + sort (p: q: p < q) [ 5 3 7 ] + => [ 3 5 7 ] + ``` - Type: - sort :: (a -> a -> Bool) -> [a] -> [a] + ::: */ sort = builtins.sort; - /* + /** Sort a list based on the default comparison of a derived property `b`. The items are returned in `b`-increasing order. @@ -614,12 +1240,33 @@ rec { sortOn f == sort (p: q: f p < f q) ``` - Example: - sortOn stringLength [ "aa" "b" "cccc" ] - => [ "b" "aa" "cccc" ] - Type: - sortOn :: (a -> b) -> [a] -> [a], for comparable b + # Inputs + + `f` + + : 1\. Function argument + + `list` + + : 2\. Function argument + + # Type + + ``` + sortOn :: (a -> b) -> [a] -> [a], for comparable b + ``` + + # Examples + :::{.example} + ## `lib.lists.sortOn` usage example + + ```nix + sortOn stringLength [ "aa" "b" "cccc" ] + => [ "b" "aa" "cccc" ] + ``` + + ::: */ sortOn = f: list: let @@ -634,17 +1281,40 @@ rec { (a: b: head a < head b) pairs); - /* Compare two lists element-by-element. + /** + Compare two lists element-by-element. + + # Inputs + + `cmp` + + : 1\. Function argument + + `a` + + : 2\. Function argument + + `b` + + : 3\. Function argument + - Example: - compareLists compare [] [] - => 0 - compareLists compare [] [ "a" ] - => -1 - compareLists compare [ "a" ] [] - => 1 - compareLists compare [ "a" "b" ] [ "a" "c" ] - => -1 + # Examples + :::{.example} + ## `lib.lists.compareLists` usage example + + ```nix + compareLists compare [] [] + => 0 + compareLists compare [] [ "a" ] + => -1 + compareLists compare [ "a" ] [] + => 1 + compareLists compare [ "a" "b" ] [ "a" "c" ] + => -1 + ``` + + ::: */ compareLists = cmp: a: b: if a == [] @@ -658,16 +1328,32 @@ rec { then compareLists cmp (tail a) (tail b) else rel; - /* Sort list using "Natural sorting". - Numeric portions of strings are sorted in numeric order. + /** + Sort list using "Natural sorting". + Numeric portions of strings are sorted in numeric order. + + + # Inputs + + `lst` + + : 1\. Function argument + - Example: - naturalSort ["disk11" "disk8" "disk100" "disk9"] - => ["disk8" "disk9" "disk11" "disk100"] - naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"] - => ["10.5.16.62" "10.46.133.149" "10.54.16.25"] - naturalSort ["v0.2" "v0.15" "v0.0.9"] - => [ "v0.0.9" "v0.2" "v0.15" ] + # Examples + :::{.example} + ## `lib.lists.naturalSort` usage example + + ```nix + naturalSort ["disk11" "disk8" "disk100" "disk9"] + => ["disk8" "disk9" "disk11" "disk100"] + naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"] + => ["10.5.16.62" "10.46.133.149" "10.54.16.25"] + naturalSort ["v0.2" "v0.15" "v0.0.9"] + => [ "v0.0.9" "v0.2" "v0.15" ] + ``` + + ::: */ naturalSort = lst: let @@ -677,61 +1363,149 @@ rec { in map (x: elemAt x 1) (sort less prepared); - /* Return the first (at most) N elements of a list. + /** + Return the first (at most) N elements of a list. + + + # Inputs + + `count` + + : Number of elements to take + + `list` - Type: take :: int -> [a] -> [a] + : Input list - Example: - take 2 [ "a" "b" "c" "d" ] - => [ "a" "b" ] - take 2 [ ] - => [ ] + # Type + + ``` + take :: int -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.take` usage example + + ```nix + take 2 [ "a" "b" "c" "d" ] + => [ "a" "b" ] + take 2 [ ] + => [ ] + ``` + + ::: */ take = - # Number of elements to take count: sublist 0 count; - /* Remove the first (at most) N elements of a list. + /** + Remove the first (at most) N elements of a list. - Type: drop :: int -> [a] -> [a] - Example: - drop 2 [ "a" "b" "c" "d" ] - => [ "c" "d" ] - drop 2 [ ] - => [ ] + # Inputs + + `count` + + : Number of elements to drop + + `list` + + : Input list + + # Type + + ``` + drop :: int -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.drop` usage example + + ```nix + drop 2 [ "a" "b" "c" "d" ] + => [ "c" "d" ] + drop 2 [ ] + => [ ] + ``` + + ::: */ drop = - # Number of elements to drop count: - # Input list list: sublist count (length list) list; - /* Whether the first list is a prefix of the second list. + /** + Whether the first list is a prefix of the second list. + + + # Inputs + + `list1` - Type: hasPrefix :: [a] -> [a] -> bool + : 1\. Function argument - Example: + `list2` + + : 2\. Function argument + + # Type + + ``` + hasPrefix :: [a] -> [a] -> bool + ``` + + # Examples + :::{.example} + ## `lib.lists.hasPrefix` usage example + + ```nix hasPrefix [ 1 2 ] [ 1 2 3 4 ] => true hasPrefix [ 0 1 ] [ 1 2 3 4 ] => false + ``` + + ::: */ hasPrefix = list1: list2: take (length list1) list2 == list1; - /* Remove the first list as a prefix from the second list. - Error if the first list isn't a prefix of the second list. + /** + Remove the first list as a prefix from the second list. + Error if the first list isn't a prefix of the second list. + + # Inputs + + `list1` + + : 1\. Function argument + + `list2` - Type: removePrefix :: [a] -> [a] -> [a] + : 2\. Function argument + + # Type + + ``` + removePrefix :: [a] -> [a] -> [a] + ``` - Example: + # Examples + :::{.example} + ## `lib.lists.removePrefix` usage example + + ```nix removePrefix [ 1 2 ] [ 1 2 3 4 ] => [ 3 4 ] removePrefix [ 0 1 ] [ 1 2 3 4 ] => <error> + ``` + + ::: */ removePrefix = list1: @@ -741,23 +1515,46 @@ rec { else throw "lib.lists.removePrefix: First argument is not a list prefix of the second argument"; - /* Return a list consisting of at most `count` elements of `list`, - starting at index `start`. + /** + Return a list consisting of at most `count` elements of `list`, + starting at index `start`. + + # Inputs + + `start` + + : Index at which to start the sublist + + `count` - Type: sublist :: int -> int -> [a] -> [a] + : Number of elements to take - Example: - sublist 1 3 [ "a" "b" "c" "d" "e" ] - => [ "b" "c" "d" ] - sublist 1 3 [ ] - => [ ] + `list` + + : Input list + + # Type + + ``` + sublist :: int -> int -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.sublist` usage example + + ```nix + sublist 1 3 [ "a" "b" "c" "d" "e" ] + => [ "b" "c" "d" ] + sublist 1 3 [ ] + => [ ] + ``` + + ::: */ sublist = - # Index at which to start the sublist start: - # Number of elements to take count: - # Input list list: let len = length list; in genList @@ -766,17 +1563,40 @@ rec { else if start + count > len then len - start else count); - /* The common prefix of two lists. + /** + The common prefix of two lists. + + + # Inputs + + `list1` - Type: commonPrefix :: [a] -> [a] -> [a] + : 1\. Function argument - Example: + `list2` + + : 2\. Function argument + + # Type + + ``` + commonPrefix :: [a] -> [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.commonPrefix` usage example + + ```nix 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: @@ -792,87 +1612,225 @@ rec { in take commonPrefixLength list1; - /* Return the last element of a list. + /** + Return the last element of a list. + + This function throws an error if the list is empty. + + + # Inputs - This function throws an error if the list is empty. + `list` - Type: last :: [a] -> a + : 1\. Function argument + + # Type + + ``` + last :: [a] -> a + ``` + + # Examples + :::{.example} + ## `lib.lists.last` usage example + + ```nix + last [ 1 2 3 ] + => 3 + ``` - Example: - last [ 1 2 3 ] - => 3 + ::: */ last = list: assert lib.assertMsg (list != []) "lists.last: list must not be empty!"; elemAt list (length list - 1); - /* Return all elements but the last. + /** + Return all elements but the last. - This function throws an error if the list is empty. + This function throws an error if the list is empty. - Type: init :: [a] -> [a] - Example: - init [ 1 2 3 ] - => [ 1 2 ] + # Inputs + + `list` + + : 1\. Function argument + + # Type + + ``` + init :: [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.init` usage example + + ```nix + init [ 1 2 3 ] + => [ 1 2 ] + ``` + + ::: */ init = list: assert lib.assertMsg (list != []) "lists.init: list must not be empty!"; take (length list - 1) list; - /* Return the image of the cross product of some lists by a function. + /** + Return the image of the cross product of some lists by a function. + + + # Examples + :::{.example} + ## `lib.lists.crossLists` usage example - Example: - crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]] - => [ "13" "14" "23" "24" ] + ```nix + crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]] + => [ "13" "14" "23" "24" ] + ``` + + ::: */ crossLists = warn "lib.crossLists is deprecated, use lib.cartesianProductOfSets instead." (f: foldl (fs: args: concatMap (f: map f args) fs) [f]); - /* Remove duplicate elements from the list. O(n^2) complexity. + /** + Remove duplicate elements from the `list`. O(n^2) complexity. + - Type: unique :: [a] -> [a] + # Inputs - Example: - unique [ 3 2 3 4 ] - => [ 3 2 4 ] - */ + `list` + + : Input list + + # Type + + ``` + unique :: [a] -> [a] + ``` + + # Examples + :::{.example} + ## `lib.lists.unique` usage example + + ```nix + unique [ 3 2 3 4 ] + => [ 3 2 4 ] + ``` + + ::: + */ unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) []; - /* Check if list contains only unique elements. O(n^2) complexity. + /** + Check if list contains only unique elements. O(n^2) complexity. + + + # Inputs + + `list` + + : 1\. Function argument + + # Type + + ``` + allUnique :: [a] -> bool + ``` - Type: allUnique :: [a] -> bool + # Examples + :::{.example} + ## `lib.lists.allUnique` usage example - Example: - allUnique [ 3 2 3 4 ] - => false - allUnique [ 3 2 4 1 ] - => true - */ + ```nix + allUnique [ 3 2 3 4 ] + => false + allUnique [ 3 2 4 1 ] + => true + ``` + + ::: + */ allUnique = list: (length (unique list) == length list); - /* Intersects list 'e' and another list. O(nm) complexity. + /** + Intersects list 'list1' and another list (`list2`). + + O(nm) complexity. - Example: - intersectLists [ 1 2 3 ] [ 6 3 2 ] - => [ 3 2 ] + # Inputs + + `list1` + + : First list + + `list2` + + : Second list + + + # Examples + :::{.example} + ## `lib.lists.intersectLists` usage example + + ```nix + intersectLists [ 1 2 3 ] [ 6 3 2 ] + => [ 3 2 ] + ``` + + ::: */ intersectLists = e: filter (x: elem x e); - /* Subtracts list 'e' from another list. O(nm) complexity. + /** + Subtracts list 'e' from another list (`list2`). + + O(nm) complexity. + + # Inputs + + `e` + + : First list + + `list2` + + : Second list + + + # Examples + :::{.example} + ## `lib.lists.subtractLists` usage example - Example: - subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ] - => [ 1 4 5 ] + ```nix + subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ] + => [ 1 4 5 ] + ``` + + ::: */ subtractLists = e: filter (x: !(elem x e)); - /* Test if two lists have no common element. - It should be slightly more efficient than (intersectLists a b == []) + /** + Test if two lists have no common element. + It should be slightly more efficient than (intersectLists a b == []) + + # Inputs + + `a` + + : 1\. Function argument + + `b` + + : 2\. Function argument */ mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b); |