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 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}