lib/fixed-points.nix

   1 { lib, ... }:
   2 rec {
   3   /*
   4     `fix f` computes the fixed point of the given function `f`. In other words, the return value is `x` in `x = f x`.
   5
   6     `f` must be a lazy function.
   7     This means that `x` must be a value that can be partially evaluated,
   8     such as an attribute set, a list, or a function.
   9     This way, `f` can use one part of `x` to compute another part.
  10
  11     **Relation to syntactic recursion**
  12
  13     This section explains `fix` by refactoring from syntactic recursion to a call of `fix` instead.
  14
  15     For context, Nix lets you define attributes in terms of other attributes syntactically using the [`rec { }` syntax](https://nixos.org/manual/nix/stable/language/constructs.html#recursive-sets).
  16
  17     ```nix
  18     nix-repl> rec {
  19       foo = "foo";
  20       bar = "bar";
  21       foobar = foo + bar;
  22     }
  23     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  24     ```
  25
  26     This is convenient when constructing a value to pass to a function for example,
  27     but an equivalent effect can be achieved with the `let` binding syntax:
  28
  29     ```nix
  30     nix-repl> let self = {
  31       foo = "foo";
  32       bar = "bar";
  33       foobar = self.foo + self.bar;
  34     }; in self
  35     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  36     ```
  37
  38     But in general you can get more reuse out of `let` bindings by refactoring them to a function.
  39
  40     ```nix
  41     nix-repl> f = self: {
  42       foo = "foo";
  43       bar = "bar";
  44       foobar = self.foo + self.bar;
  45     }
  46     ```
  47
  48     This is where `fix` comes in, it contains the syntactic recursion that's not in `f` anymore.
  49
  50     ```nix
  51     nix-repl> fix = f:
  52       let self = f self; in self;
  53     ```
  54
  55     By applying `fix` we get the final result.
  56
  57     ```nix
  58     nix-repl> fix f
  59     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  60     ```
  61
  62     Such a refactored `f` using `fix` is not useful by itself.
  63     See [`extends`](#function-library-lib.fixedPoints.extends) for an example use case.
  64     There `self` is also often called `final`.
  65
  66     Type: fix :: (a -> a) -> a
  67
  68     Example:
  69       fix (self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; })
  70       => { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  71
  72       fix (self: [ 1 2 (elemAt self 0 + elemAt self 1) ])
  73       => [ 1 2 3 ]
  74   */
  75   fix = f: let x = f x; in x;
  76
  77   /*
  78     A variant of `fix` that records the original recursive attribute set in the
  79     result, in an attribute named `__unfix__`.
  80
  81     This is useful in combination with the `extends` function to
  82     implement deep overriding.
  83   */
  84   fix' = f: let x = f x // { __unfix__ = f; }; in x;
  85
  86   /*
  87     Return the fixpoint that `f` converges to when called iteratively, starting
  88     with the input `x`.
  89
  90     ```
  91     nix-repl> converge (x: x / 2) 16
  92     0
  93     ```
  94
  95     Type: (a -> a) -> a -> a
  96   */
  97   converge = f: x:
  98     let
  99       x' = f x;
 100     in
 101       if x' == x
 102       then x
 103       else converge f x';
 104
 105   /*
 106     Extend a function using an overlay.
 107
 108     Overlays allow modifying and extending fixed-point functions, specifically ones returning attribute sets.
 109     A fixed-point function is a function which is intended to be evaluated by passing the result of itself as the argument.
 110     This is possible due to Nix's lazy evaluation.
 111
 112
 113     A fixed-point function returning an attribute set has the form
 114
 115     ```nix
 116     final: { # attributes }
 117     ```
 118
 119     where `final` refers to the lazily evaluated attribute set returned by the fixed-point function.
 120
 121     An overlay to such a fixed-point function has the form
 122
 123     ```nix
 124     final: prev: { # attributes }
 125     ```
 126
 127     where `prev` refers to the result of the original function to `final`, and `final` is the result of the composition of the overlay and the original function.
 128
 129     Applying an overlay is done with `extends`:
 130
 131     ```nix
 132     let
 133       f = final: { # attributes };
 134       overlay = final: prev: { # attributes };
 135     in extends overlay f;
 136     ```
 137
 138     To get the value of `final`, use `lib.fix`:
 139
 140     ```nix
 141     let
 142       f = final: { # attributes };
 143       overlay = final: prev: { # attributes };
 144       g = extends overlay f;
 145     in fix g
 146     ```
 147
 148     :::{.note}
 149     The argument to the given fixed-point function after applying an overlay will *not* refer to its own return value, but rather to the value after evaluating the overlay function.
 150
 151     The given fixed-point function is called with a separate argument than if it was evaluated with `lib.fix`.
 152     :::
 153
 154     :::{.example}
 155
 156     # Extend a fixed-point function with an overlay
 157
 158     Define a fixed-point function `f` that expects its own output as the argument `final`:
 159
 160     ```nix-repl
 161     f = final: {
 162       # Constant value a
 163       a = 1;
 164
 165       # b depends on the final value of a, available as final.a
 166       b = final.a + 2;
 167     }
 168     ```
 169
 170     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) to get the final result:
 171
 172     ```nix-repl
 173     fix f
 174     => { a = 1; b = 3; }
 175     ```
 176
 177     An overlay represents a modification or extension of such a fixed-point function.
 178     Here's an example of an overlay:
 179
 180     ```nix-repl
 181     overlay = final: prev: {
 182       # Modify the previous value of a, available as prev.a
 183       a = prev.a + 10;
 184
 185       # Extend the attribute set with c, letting it depend on the final values of a and b
 186       c = final.a + final.b;
 187     }
 188     ```
 189
 190     Use `extends overlay f` to apply the overlay to the fixed-point function `f`.
 191     This produces a new fixed-point function `g` with the combined behavior of `f` and `overlay`:
 192
 193     ```nix-repl
 194     g = extends overlay f
 195     ```
 196
 197     The result is a function, so we can't print it directly, but it's the same as:
 198
 199     ```nix-repl
 200     g' = final: {
 201       # The constant from f, but changed with the overlay
 202       a = 1 + 10;
 203
 204       # Unchanged from f
 205       b = final.a + 2;
 206
 207       # Extended in the overlay
 208       c = final.a + final.b;
 209     }
 210     ```
 211
 212     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) again to get the final result:
 213
 214     ```nix-repl
 215     fix g
 216     => { a = 11; b = 13; c = 24; }
 217     ```
 218     :::
 219
 220     Type:
 221       extends :: (Attrs -> Attrs -> Attrs) # The overlay to apply to the fixed-point function
 222               -> (Attrs -> Attrs) # A fixed-point function
 223               -> (Attrs -> Attrs) # The resulting fixed-point function
 224
 225     Example:
 226       f = final: { a = 1; b = final.a + 2; }
 227
 228       fix f
 229       => { a = 1; b = 3; }
 230
 231       fix (extends (final: prev: { a = prev.a + 10; }) f)
 232       => { a = 11; b = 13; }
 233
 234       fix (extends (final: prev: { b = final.a + 5; }) f)
 235       => { a = 1; b = 6; }
 236
 237       fix (extends (final: prev: { c = final.a + final.b; }) f)
 238       => { a = 1; b = 3; c = 4; }
 239   */
 240   extends =
 241     # The overlay to apply to the fixed-point function
 242     overlay:
 243     # The fixed-point function
 244     f:
 245     # Wrap with parenthesis to prevent nixdoc from rendering the `final` argument in the documentation
 246     # The result should be thought of as a function, the argument of that function is not an argument to `extends` itself
 247     (
 248       final:
 249       let
 250         prev = f final;
 251       in
 252       prev // overlay final prev
 253     );
 254
 255   /*
 256     Compose two extending functions of the type expected by 'extends'
 257     into one where changes made in the first are available in the
 258     'super' of the second
 259   */
 260   composeExtensions =
 261     f: g: final: prev:
 262       let fApplied = f final prev;
 263           prev' = prev // fApplied;
 264       in fApplied // g final prev';
 265
 266   /*
 267     Compose several extending functions of the type expected by 'extends' into
 268     one where changes made in preceding functions are made available to
 269     subsequent ones.
 270
 271     ```
 272     composeManyExtensions : [packageSet -> packageSet -> packageSet] -> packageSet -> packageSet -> packageSet
 273                               ^final        ^prev         ^overrides     ^final        ^prev         ^overrides
 274     ```
 275   */
 276   composeManyExtensions =
 277     lib.foldr (x: y: composeExtensions x y) (final: prev: {});
 278
 279   /*
 280     Create an overridable, recursive attribute set. For example:
 281
 282     ```
 283     nix-repl> obj = makeExtensible (self: { })
 284
 285     nix-repl> obj
 286     { __unfix__ = «lambda»; extend = «lambda»; }
 287
 288     nix-repl> obj = obj.extend (self: super: { foo = "foo"; })
 289
 290     nix-repl> obj
 291     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 292
 293     nix-repl> obj = obj.extend (self: super: { foo = super.foo + " + "; bar = "bar"; foobar = self.foo + self.bar; })
 294
 295     nix-repl> obj
 296     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 297     ```
 298   */
 299   makeExtensible = makeExtensibleWithCustomName "extend";
 300
 301   /*
 302     Same as `makeExtensible` but the name of the extending attribute is
 303     customized.
 304   */
 305   makeExtensibleWithCustomName = extenderName: rattrs:
 306     fix' (self: (rattrs self) // {
 307       ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 308     });
 309 }