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
  67     # Inputs
  68
  69     `f`
  70
  71     : 1\. Function argument
  72
  73     # Type
  74
  75     ```
  76     fix :: (a -> a) -> a
  77     ```
  78
  79     # Examples
  80     :::{.example}
  81     ## `lib.fixedPoints.fix` usage example
  82
  83     ```nix
  84     fix (self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; })
  85     => { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  86
  87     fix (self: [ 1 2 (elemAt self 0 + elemAt self 1) ])
  88     => [ 1 2 3 ]
  89     ```
  90
  91     :::
  92   */
  93   fix = f: let x = f x; in x;
  94
  95   /**
  96     A variant of `fix` that records the original recursive attribute set in the
  97     result, in an attribute named `__unfix__`.
  98
  99     This is useful in combination with the `extends` function to
 100     implement deep overriding.
 101
 102
 103     # Inputs
 104
 105     `f`
 106
 107     : 1\. Function argument
 108   */
 109   fix' = f: let x = f x // { __unfix__ = f; }; in x;
 110
 111   /**
 112     Return the fixpoint that `f` converges to when called iteratively, starting
 113     with the input `x`.
 114
 115     ```
 116     nix-repl> converge (x: x / 2) 16
 117     0
 118     ```
 119
 120
 121     # Inputs
 122
 123     `f`
 124
 125     : 1\. Function argument
 126
 127     `x`
 128
 129     : 2\. Function argument
 130
 131     # Type
 132
 133     ```
 134     (a -> a) -> a -> a
 135     ```
 136   */
 137   converge = f: x:
 138     let
 139       x' = f x;
 140     in
 141       if x' == x
 142       then x
 143       else converge f x';
 144
 145   /**
 146     Extend a function using an overlay.
 147
 148     Overlays allow modifying and extending fixed-point functions, specifically ones returning attribute sets.
 149     A fixed-point function is a function which is intended to be evaluated by passing the result of itself as the argument.
 150     This is possible due to Nix's lazy evaluation.
 151
 152
 153     A fixed-point function returning an attribute set has the form
 154
 155     ```nix
 156     final: { # attributes }
 157     ```
 158
 159     where `final` refers to the lazily evaluated attribute set returned by the fixed-point function.
 160
 161     An overlay to such a fixed-point function has the form
 162
 163     ```nix
 164     final: prev: { # attributes }
 165     ```
 166
 167     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.
 168
 169     Applying an overlay is done with `extends`:
 170
 171     ```nix
 172     let
 173       f = final: { # attributes };
 174       overlay = final: prev: { # attributes };
 175     in extends overlay f;
 176     ```
 177
 178     To get the value of `final`, use `lib.fix`:
 179
 180     ```nix
 181     let
 182       f = final: { # attributes };
 183       overlay = final: prev: { # attributes };
 184       g = extends overlay f;
 185     in fix g
 186     ```
 187
 188     :::{.note}
 189     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.
 190
 191     The given fixed-point function is called with a separate argument than if it was evaluated with `lib.fix`.
 192     :::
 193
 194     :::{.example}
 195
 196     # Extend a fixed-point function with an overlay
 197
 198     Define a fixed-point function `f` that expects its own output as the argument `final`:
 199
 200     ```nix-repl
 201     f = final: {
 202       # Constant value a
 203       a = 1;
 204
 205       # b depends on the final value of a, available as final.a
 206       b = final.a + 2;
 207     }
 208     ```
 209
 210     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) to get the final result:
 211
 212     ```nix-repl
 213     fix f
 214     => { a = 1; b = 3; }
 215     ```
 216
 217     An overlay represents a modification or extension of such a fixed-point function.
 218     Here's an example of an overlay:
 219
 220     ```nix-repl
 221     overlay = final: prev: {
 222       # Modify the previous value of a, available as prev.a
 223       a = prev.a + 10;
 224
 225       # Extend the attribute set with c, letting it depend on the final values of a and b
 226       c = final.a + final.b;
 227     }
 228     ```
 229
 230     Use `extends overlay f` to apply the overlay to the fixed-point function `f`.
 231     This produces a new fixed-point function `g` with the combined behavior of `f` and `overlay`:
 232
 233     ```nix-repl
 234     g = extends overlay f
 235     ```
 236
 237     The result is a function, so we can't print it directly, but it's the same as:
 238
 239     ```nix-repl
 240     g' = final: {
 241       # The constant from f, but changed with the overlay
 242       a = 1 + 10;
 243
 244       # Unchanged from f
 245       b = final.a + 2;
 246
 247       # Extended in the overlay
 248       c = final.a + final.b;
 249     }
 250     ```
 251
 252     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) again to get the final result:
 253
 254     ```nix-repl
 255     fix g
 256     => { a = 11; b = 13; c = 24; }
 257     ```
 258     :::
 259
 260
 261     # Inputs
 262
 263     `overlay`
 264
 265     : The overlay to apply to the fixed-point function
 266
 267     `f`
 268
 269     : The fixed-point function
 270
 271     # Type
 272
 273     ```
 274     extends :: (Attrs -> Attrs -> Attrs) # The overlay to apply to the fixed-point function
 275             -> (Attrs -> Attrs) # A fixed-point function
 276             -> (Attrs -> Attrs) # The resulting fixed-point function
 277     ```
 278
 279     # Examples
 280     :::{.example}
 281     ## `lib.fixedPoints.extends` usage example
 282
 283     ```nix
 284     f = final: { a = 1; b = final.a + 2; }
 285
 286     fix f
 287     => { a = 1; b = 3; }
 288
 289     fix (extends (final: prev: { a = prev.a + 10; }) f)
 290     => { a = 11; b = 13; }
 291
 292     fix (extends (final: prev: { b = final.a + 5; }) f)
 293     => { a = 1; b = 6; }
 294
 295     fix (extends (final: prev: { c = final.a + final.b; }) f)
 296     => { a = 1; b = 3; c = 4; }
 297     ```
 298
 299     :::
 300   */
 301   extends =
 302     overlay:
 303     f:
 304     # The result should be thought of as a function, the argument of that function is not an argument to `extends` itself
 305     (
 306       final:
 307       let
 308         prev = f final;
 309       in
 310       prev // overlay final prev
 311     );
 312
 313   /**
 314     Compose two extending functions of the type expected by 'extends'
 315     into one where changes made in the first are available in the
 316     'super' of the second
 317
 318
 319     # Inputs
 320
 321     `f`
 322
 323     : 1\. Function argument
 324
 325     `g`
 326
 327     : 2\. Function argument
 328
 329     `final`
 330
 331     : 3\. Function argument
 332
 333     `prev`
 334
 335     : 4\. Function argument
 336   */
 337   composeExtensions =
 338     f: g: final: prev:
 339       let fApplied = f final prev;
 340           prev' = prev // fApplied;
 341       in fApplied // g final prev';
 342
 343   /**
 344     Compose several extending functions of the type expected by 'extends' into
 345     one where changes made in preceding functions are made available to
 346     subsequent ones.
 347
 348     ```
 349     composeManyExtensions : [packageSet -> packageSet -> packageSet] -> packageSet -> packageSet -> packageSet
 350                               ^final        ^prev         ^overrides     ^final        ^prev         ^overrides
 351     ```
 352   */
 353   composeManyExtensions =
 354     lib.foldr (x: y: composeExtensions x y) (final: prev: {});
 355
 356   /**
 357     Create an overridable, recursive attribute set. For example:
 358
 359     ```
 360     nix-repl> obj = makeExtensible (self: { })
 361
 362     nix-repl> obj
 363     { __unfix__ = «lambda»; extend = «lambda»; }
 364
 365     nix-repl> obj = obj.extend (self: super: { foo = "foo"; })
 366
 367     nix-repl> obj
 368     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 369
 370     nix-repl> obj = obj.extend (self: super: { foo = super.foo + " + "; bar = "bar"; foobar = self.foo + self.bar; })
 371
 372     nix-repl> obj
 373     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 374     ```
 375   */
 376   makeExtensible = makeExtensibleWithCustomName "extend";
 377
 378   /**
 379     Same as `makeExtensible` but the name of the extending attribute is
 380     customized.
 381
 382
 383     # Inputs
 384
 385     `extenderName`
 386
 387     : 1\. Function argument
 388
 389     `rattrs`
 390
 391     : 2\. Function argument
 392   */
 393   makeExtensibleWithCustomName = extenderName: rattrs:
 394     fix' (self: (rattrs self) // {
 395       ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 396     });
 397 }