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     # Inputs
  67
  68     `f`
  69
  70     : 1\. Function argument
  71
  72     # Type
  73
  74     ```
  75     fix :: (a -> a) -> a
  76     ```
  77
  78     # Examples
  79     :::{.example}
  80     ## `lib.fixedPoints.fix` usage example
  81
  82     ```nix
  83     fix (self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; })
  84     => { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  85
  86     fix (self: [ 1 2 (elemAt self 0 + elemAt self 1) ])
  87     => [ 1 2 3 ]
  88     ```
  89
  90     :::
  91   */
  92   fix =
  93     f:
  94     let
  95       x = f x;
  96     in
  97     x;
  98
  99   /**
 100     A variant of `fix` that records the original recursive attribute set in the
 101     result, in an attribute named `__unfix__`.
 102
 103     This is useful in combination with the `extends` function to
 104     implement deep overriding.
 105
 106     # Inputs
 107
 108     `f`
 109
 110     : 1\. Function argument
 111   */
 112   fix' =
 113     f:
 114     let
 115       x = f x // {
 116         __unfix__ = f;
 117       };
 118     in
 119     x;
 120
 121   /**
 122     Return the fixpoint that `f` converges to when called iteratively, starting
 123     with the input `x`.
 124
 125     ```
 126     nix-repl> converge (x: x / 2) 16
 127     0
 128     ```
 129
 130     # Inputs
 131
 132     `f`
 133
 134     : 1\. Function argument
 135
 136     `x`
 137
 138     : 2\. Function argument
 139
 140     # Type
 141
 142     ```
 143     (a -> a) -> a -> a
 144     ```
 145   */
 146   converge =
 147     f: x:
 148     let
 149       x' = f x;
 150     in
 151     if x' == x then x else converge f x';
 152
 153   /**
 154     Extend a function using an overlay.
 155
 156     Overlays allow modifying and extending fixed-point functions, specifically ones returning attribute sets.
 157     A fixed-point function is a function which is intended to be evaluated by passing the result of itself as the argument.
 158     This is possible due to Nix's lazy evaluation.
 159
 160     A fixed-point function returning an attribute set has the form
 161
 162     ```nix
 163     final: {
 164       # attributes
 165     }
 166     ```
 167
 168     where `final` refers to the lazily evaluated attribute set returned by the fixed-point function.
 169
 170     An overlay to such a fixed-point function has the form
 171
 172     ```nix
 173     final: prev: {
 174       # attributes
 175     }
 176     ```
 177
 178     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.
 179
 180     Applying an overlay is done with `extends`:
 181
 182     ```nix
 183     let
 184       f = final: {
 185         # attributes
 186       };
 187       overlay = final: prev: {
 188         # attributes
 189       };
 190     in extends overlay f;
 191     ```
 192
 193     To get the value of `final`, use `lib.fix`:
 194
 195     ```nix
 196     let
 197       f = final: {
 198         # attributes
 199       };
 200       overlay = final: prev: {
 201         # attributes
 202       };
 203       g = extends overlay f;
 204     in fix g
 205     ```
 206
 207     :::{.note}
 208     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.
 209
 210     The given fixed-point function is called with a separate argument than if it was evaluated with `lib.fix`.
 211     :::
 212
 213     :::{.example}
 214
 215     # Extend a fixed-point function with an overlay
 216
 217     Define a fixed-point function `f` that expects its own output as the argument `final`:
 218
 219     ```nix-repl
 220     f = final: {
 221       # Constant value a
 222       a = 1;
 223
 224       # b depends on the final value of a, available as final.a
 225       b = final.a + 2;
 226     }
 227     ```
 228
 229     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) to get the final result:
 230
 231     ```nix-repl
 232     fix f
 233     => { a = 1; b = 3; }
 234     ```
 235
 236     An overlay represents a modification or extension of such a fixed-point function.
 237     Here's an example of an overlay:
 238
 239     ```nix-repl
 240     overlay = final: prev: {
 241       # Modify the previous value of a, available as prev.a
 242       a = prev.a + 10;
 243
 244       # Extend the attribute set with c, letting it depend on the final values of a and b
 245       c = final.a + final.b;
 246     }
 247     ```
 248
 249     Use `extends overlay f` to apply the overlay to the fixed-point function `f`.
 250     This produces a new fixed-point function `g` with the combined behavior of `f` and `overlay`:
 251
 252     ```nix-repl
 253     g = extends overlay f
 254     ```
 255
 256     The result is a function, so we can't print it directly, but it's the same as:
 257
 258     ```nix-repl
 259     g' = final: {
 260       # The constant from f, but changed with the overlay
 261       a = 1 + 10;
 262
 263       # Unchanged from f
 264       b = final.a + 2;
 265
 266       # Extended in the overlay
 267       c = final.a + final.b;
 268     }
 269     ```
 270
 271     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) again to get the final result:
 272
 273     ```nix-repl
 274     fix g
 275     => { a = 11; b = 13; c = 24; }
 276     ```
 277     :::
 278
 279     # Inputs
 280
 281     `overlay`
 282
 283     : The overlay to apply to the fixed-point function
 284
 285     `f`
 286
 287     : The fixed-point function
 288
 289     # Type
 290
 291     ```
 292     extends :: (Attrs -> Attrs -> Attrs) # The overlay to apply to the fixed-point function
 293             -> (Attrs -> Attrs) # A fixed-point function
 294             -> (Attrs -> Attrs) # The resulting fixed-point function
 295     ```
 296
 297     # Examples
 298     :::{.example}
 299     ## `lib.fixedPoints.extends` usage example
 300
 301     ```nix
 302     f = final: { a = 1; b = final.a + 2; }
 303
 304     fix f
 305     => { a = 1; b = 3; }
 306
 307     fix (extends (final: prev: { a = prev.a + 10; }) f)
 308     => { a = 11; b = 13; }
 309
 310     fix (extends (final: prev: { b = final.a + 5; }) f)
 311     => { a = 1; b = 6; }
 312
 313     fix (extends (final: prev: { c = final.a + final.b; }) f)
 314     => { a = 1; b = 3; c = 4; }
 315     ```
 316
 317     :::
 318   */
 319   extends =
 320     overlay: f:
 321     # The result should be thought of as a function, the argument of that function is not an argument to `extends` itself
 322     (
 323       final:
 324       let
 325         prev = f final;
 326       in
 327       prev // overlay final prev
 328     );
 329
 330   /**
 331     Compose two overlay functions and return a single overlay function that combines them.
 332     For more details see: [composeManyExtensions](#function-library-lib.fixedPoints.composeManyExtensions).
 333   */
 334   composeExtensions =
 335     f: g: final: prev:
 336     let
 337       fApplied = f final prev;
 338       prev' = prev // fApplied;
 339     in
 340     fApplied // g final prev';
 341
 342   /**
 343     Composes a list of [`overlays`](#chap-overlays) and returns a single overlay function that combines them.
 344
 345     :::{.note}
 346     The result is produced by using the update operator `//`.
 347     This means nested values of previous overlays are not merged recursively.
 348     In other words, previously defined attributes are replaced, ignoring the previous value, unless referenced by the overlay; for example `final: prev: { foo = final.foo + 1; }`.
 349     :::
 350
 351     # Inputs
 352
 353     `extensions`
 354
 355     : A list of overlay functions
 356       :::{.note}
 357       The order of the overlays in the list is important.
 358       :::
 359
 360     : Each overlay function takes two arguments, by convention `final` and `prev`, and returns an attribute set.
 361       - `final` is the result of the fixed-point function, with all overlays applied.
 362       - `prev` is the result of the previous overlay function(s).
 363
 364     # Type
 365
 366     ```
 367     # Pseudo code
 368     let
 369       #               final      prev
 370       #                 ↓          ↓
 371       OverlayFn = { ... } -> { ... } -> { ... };
 372     in
 373       composeManyExtensions :: ListOf OverlayFn -> OverlayFn
 374     ```
 375
 376     # Examples
 377     :::{.example}
 378     ## `lib.fixedPoints.composeManyExtensions` usage example
 379
 380     ```nix
 381     let
 382       # The "original function" that is extended by the overlays.
 383       # Note that it doesn't have prev: as argument since no overlay function precedes it.
 384       original = final: { a = 1; };
 385
 386       # Each overlay function has 'final' and 'prev' as arguments.
 387       overlayA = final: prev: { b = final.c; c = 3; };
 388       overlayB = final: prev: { c = 10; x = prev.c or 5; };
 389
 390       extensions = composeManyExtensions [ overlayA overlayB ];
 391
 392       # Caluculate the fixed point of all composed overlays.
 393       fixedpoint = lib.fix (lib.extends extensions original );
 394
 395     in fixedpoint
 396     =>
 397     {
 398       a = 1;
 399       b = 10;
 400       c = 10;
 401       x = 3;
 402     }
 403     ```
 404     :::
 405   */
 406   composeManyExtensions = lib.foldr (x: y: composeExtensions x y) (final: prev: { });
 407
 408   /**
 409     Create an overridable, recursive attribute set. For example:
 410
 411     ```
 412     nix-repl> obj = makeExtensible (final: { })
 413
 414     nix-repl> obj
 415     { __unfix__ = «lambda»; extend = «lambda»; }
 416
 417     nix-repl> obj = obj.extend (final: prev: { foo = "foo"; })
 418
 419     nix-repl> obj
 420     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 421
 422     nix-repl> obj = obj.extend (final: prev: { foo = prev.foo + " + "; bar = "bar"; foobar = final.foo + final.bar; })
 423
 424     nix-repl> obj
 425     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 426     ```
 427   */
 428   makeExtensible = makeExtensibleWithCustomName "extend";
 429
 430   /**
 431     Same as `makeExtensible` but the name of the extending attribute is
 432     customized.
 433
 434     # Inputs
 435
 436     `extenderName`
 437
 438     : 1\. Function argument
 439
 440     `rattrs`
 441
 442     : 2\. Function argument
 443   */
 444   makeExtensibleWithCustomName =
 445     extenderName: rattrs:
 446     fix' (
 447       self:
 448       (rattrs self)
 449       // {
 450         ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 451       }
 452     );
 453
 454   /**
 455     Convert to an extending function (overlay).
 456
 457     `toExtension` is the `toFunction` for extending functions (a.k.a. extensions or overlays).
 458     It converts a non-function or a single-argument function to an extending function,
 459     while returning a two-argument function as-is.
 460
 461     That is, it takes a value of the shape `x`, `prev: x`, or `final: prev: x`,
 462     and returns `final: prev: x`, assuming `x` is not a function.
 463
 464     This function takes care of the input to `stdenv.mkDerivation`'s
 465     `overrideAttrs` function.
 466     It bridges the gap between `<pkg>.overrideAttrs`
 467     before and after the overlay-style support.
 468
 469     # Inputs
 470
 471     `f`
 472     : The function or value to convert to an extending function.
 473
 474     # Type
 475
 476     ```
 477     toExtension ::
 478       b' -> Any -> Any -> b'
 479     or
 480     toExtension ::
 481       (a -> b') -> Any -> a -> b'
 482     or
 483     toExtension ::
 484       (a -> a -> b) -> a -> a -> b
 485     where b' = ! Callable
 486
 487     Set a = b = b' = AttrSet & ! Callable to make toExtension return an extending function.
 488     ```
 489
 490     # Examples
 491     :::{.example}
 492     ## `lib.fixedPoints.toExtension` usage example
 493
 494     ```nix
 495     fix (final: { a = 0; c = final.a; })
 496     => { a = 0; c = 0; };
 497
 498     fix (extends (toExtension { a = 1; b = 2; }) (final: { a = 0; c = final.a; }))
 499     => { a = 1; b = 2; c = 1; };
 500
 501     fix (extends (toExtension (prev: { a = 1; b = prev.a; })) (final: { a = 0; c = final.a; }))
 502     => { a = 1; b = 0; c = 1; };
 503
 504     fix (extends (toExtension (final: prev: { a = 1; b = prev.a; c = final.a + 1 })) (final: { a = 0; c = final.a; }))
 505     => { a = 1; b = 0; c = 2; };
 506     ```
 507     :::
 508   */
 509   toExtension =
 510     f:
 511     if lib.isFunction f then
 512       final: prev:
 513       let
 514         fPrev = f prev;
 515       in
 516       if lib.isFunction fPrev then
 517         # f is (final: prev: { ... })
 518         f final prev
 519       else
 520         # f is (prev: { ... })
 521         fPrev
 522     else
 523       # f is not a function; probably { ... }
 524       final: prev: f;
 525 }