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     Modify the contents of an explicitly recursive attribute set in a way that
 107     honors `self`-references. This is accomplished with a function
 108
 109     ```nix
 110     g = self: super: { foo = super.foo + " + "; }
 111     ```
 112
 113     that has access to the unmodified input (`super`) as well as the final
 114     non-recursive representation of the attribute set (`self`). `extends`
 115     differs from the native `//` operator insofar as that it's applied *before*
 116     references to `self` are resolved:
 117
 118     ```
 119     nix-repl> fix (extends g f)
 120     { bar = "bar"; foo = "foo + "; foobar = "foo + bar"; }
 121     ```
 122
 123     The name of the function is inspired by object-oriented inheritance, i.e.
 124     think of it as an infix operator `g extends f` that mimics the syntax from
 125     Java. It may seem counter-intuitive to have the "base class" as the second
 126     argument, but it's nice this way if several uses of `extends` are cascaded.
 127
 128     To get a better understanding how `extends` turns a function with a fix
 129     point (the package set we start with) into a new function with a different fix
 130     point (the desired packages set) lets just see, how `extends g f`
 131     unfolds with `g` and `f` defined above:
 132
 133     ```
 134     extends g f = self: let super = f self; in super // g self super;
 135                 = self: let super = { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }; in super // g self super
 136                 = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // g self { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }
 137                 = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // { foo = "foo" + " + "; }
 138                 = self: { foo = "foo + "; bar = "bar"; foobar = self.foo + self.bar; }
 139     ```
 140   */
 141   extends = f: rattrs: self: let super = rattrs self; in super // f self super;
 142
 143   /*
 144     Compose two extending functions of the type expected by 'extends'
 145     into one where changes made in the first are available in the
 146     'super' of the second
 147   */
 148   composeExtensions =
 149     f: g: final: prev:
 150       let fApplied = f final prev;
 151           prev' = prev // fApplied;
 152       in fApplied // g final prev';
 153
 154   /*
 155     Compose several extending functions of the type expected by 'extends' into
 156     one where changes made in preceding functions are made available to
 157     subsequent ones.
 158
 159     ```
 160     composeManyExtensions : [packageSet -> packageSet -> packageSet] -> packageSet -> packageSet -> packageSet
 161                               ^final        ^prev         ^overrides     ^final        ^prev         ^overrides
 162     ```
 163   */
 164   composeManyExtensions =
 165     lib.foldr (x: y: composeExtensions x y) (final: prev: {});
 166
 167   /*
 168     Create an overridable, recursive attribute set. For example:
 169
 170     ```
 171     nix-repl> obj = makeExtensible (self: { })
 172
 173     nix-repl> obj
 174     { __unfix__ = «lambda»; extend = «lambda»; }
 175
 176     nix-repl> obj = obj.extend (self: super: { foo = "foo"; })
 177
 178     nix-repl> obj
 179     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 180
 181     nix-repl> obj = obj.extend (self: super: { foo = super.foo + " + "; bar = "bar"; foobar = self.foo + self.bar; })
 182
 183     nix-repl> obj
 184     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 185     ```
 186   */
 187   makeExtensible = makeExtensibleWithCustomName "extend";
 188
 189   /*
 190     Same as `makeExtensible` but the name of the extending attribute is
 191     customized.
 192   */
 193   makeExtensibleWithCustomName = extenderName: rattrs:
 194     fix' (self: (rattrs self) // {
 195       ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 196     });
 197 }