1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
{ lib, ... }:
rec {
/*
`fix f` computes the fixed point of the given function `f`. In other words, the return value is `x` in `x = f x`.
`f` must be a lazy function.
This means that `x` must be a value that can be partially evaluated,
such as an attribute set, a list, or a function.
This way, `f` can use one part of `x` to compute another part.
**Relation to syntactic recursion**
This section explains `fix` by refactoring from syntactic recursion to a call of `fix` instead.
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).
```nix
nix-repl> rec {
foo = "foo";
bar = "bar";
foobar = foo + bar;
}
{ bar = "bar"; foo = "foo"; foobar = "foobar"; }
```
This is convenient when constructing a value to pass to a function for example,
but an equivalent effect can be achieved with the `let` binding syntax:
```nix
nix-repl> let self = {
foo = "foo";
bar = "bar";
foobar = self.foo + self.bar;
}; in self
{ bar = "bar"; foo = "foo"; foobar = "foobar"; }
```
But in general you can get more reuse out of `let` bindings by refactoring them to a function.
```nix
nix-repl> f = self: {
foo = "foo";
bar = "bar";
foobar = self.foo + self.bar;
}
```
This is where `fix` comes in, it contains the syntactic recursion that's not in `f` anymore.
```nix
nix-repl> fix = f:
let self = f self; in self;
```
By applying `fix` we get the final result.
```nix
nix-repl> fix f
{ bar = "bar"; foo = "foo"; foobar = "foobar"; }
```
Such a refactored `f` using `fix` is not useful by itself.
See [`extends`](#function-library-lib.fixedPoints.extends) for an example use case.
There `self` is also often called `final`.
Type: fix :: (a -> a) -> a
Example:
fix (self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; })
=> { bar = "bar"; foo = "foo"; foobar = "foobar"; }
fix (self: [ 1 2 (elemAt self 0 + elemAt self 1) ])
=> [ 1 2 3 ]
*/
fix = f: let x = f x; in x;
/*
A variant of `fix` that records the original recursive attribute set in the
result, in an attribute named `__unfix__`.
This is useful in combination with the `extends` function to
implement deep overriding.
*/
fix' = f: let x = f x // { __unfix__ = f; }; in x;
/*
Return the fixpoint that `f` converges to when called iteratively, starting
with the input `x`.
```
nix-repl> converge (x: x / 2) 16
0
```
Type: (a -> a) -> a -> a
*/
converge = f: x:
let
x' = f x;
in
if x' == x
then x
else converge f x';
/*
Modify the contents of an explicitly recursive attribute set in a way that
honors `self`-references. This is accomplished with a function
```nix
g = self: super: { foo = super.foo + " + "; }
```
that has access to the unmodified input (`super`) as well as the final
non-recursive representation of the attribute set (`self`). `extends`
differs from the native `//` operator insofar as that it's applied *before*
references to `self` are resolved:
```
nix-repl> fix (extends g f)
{ bar = "bar"; foo = "foo + "; foobar = "foo + bar"; }
```
The name of the function is inspired by object-oriented inheritance, i.e.
think of it as an infix operator `g extends f` that mimics the syntax from
Java. It may seem counter-intuitive to have the "base class" as the second
argument, but it's nice this way if several uses of `extends` are cascaded.
To get a better understanding how `extends` turns a function with a fix
point (the package set we start with) into a new function with a different fix
point (the desired packages set) lets just see, how `extends g f`
unfolds with `g` and `f` defined above:
```
extends g f = self: let super = f self; in super // g self super;
= self: let super = { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }; in super // g self super
= self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // g self { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }
= self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // { foo = "foo" + " + "; }
= self: { foo = "foo + "; bar = "bar"; foobar = self.foo + self.bar; }
```
*/
extends = f: rattrs: self: let super = rattrs self; in super // f self super;
/*
Compose two extending functions of the type expected by 'extends'
into one where changes made in the first are available in the
'super' of the second
*/
composeExtensions =
f: g: final: prev:
let fApplied = f final prev;
prev' = prev // fApplied;
in fApplied // g final prev';
/*
Compose several extending functions of the type expected by 'extends' into
one where changes made in preceding functions are made available to
subsequent ones.
```
composeManyExtensions : [packageSet -> packageSet -> packageSet] -> packageSet -> packageSet -> packageSet
^final ^prev ^overrides ^final ^prev ^overrides
```
*/
composeManyExtensions =
lib.foldr (x: y: composeExtensions x y) (final: prev: {});
/*
Create an overridable, recursive attribute set. For example:
```
nix-repl> obj = makeExtensible (self: { })
nix-repl> obj
{ __unfix__ = «lambda»; extend = «lambda»; }
nix-repl> obj = obj.extend (self: super: { foo = "foo"; })
nix-repl> obj
{ __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
nix-repl> obj = obj.extend (self: super: { foo = super.foo + " + "; bar = "bar"; foobar = self.foo + self.bar; })
nix-repl> obj
{ __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
```
*/
makeExtensible = makeExtensibleWithCustomName "extend";
/*
Same as `makeExtensible` but the name of the extending attribute is
customized.
*/
makeExtensibleWithCustomName = extenderName: rattrs:
fix' (self: (rattrs self) // {
${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
});
}
|