pyrox.dev
1{ lib, ... }:
2rec {
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}