diff options
Diffstat (limited to 'lib/fixed-points.nix')
-rw-r--r-- | lib/fixed-points.nix | 66 |
1 files changed, 58 insertions, 8 deletions
diff --git a/lib/fixed-points.nix b/lib/fixed-points.nix index a63f349b713d0..3444e95e15ad8 100644 --- a/lib/fixed-points.nix +++ b/lib/fixed-points.nix @@ -1,26 +1,76 @@ { lib, ... }: rec { /* - Compute the fixed point of the given function `f`, which is usually an - attribute set that expects its final, non-recursive representation as an - argument: + `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"; } ``` - f = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } + + 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; + } ``` - Nix evaluates this recursion until all references to `self` have been - resolved. At that point, the final result is returned and `f x = x` holds: + This is where `fix` comes in, it contains the syntactic 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 - See https://en.wikipedia.org/wiki/Fixed-point_combinator for further - details. + 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; |