diff options
author | Alyssa Ross <hi@alyssa.is> | 2023-11-21 16:12:21 +0100 |
---|---|---|
committer | Alyssa Ross <hi@alyssa.is> | 2023-11-21 16:12:48 +0100 |
commit | 048a4cd441a59cbf89defb18bb45c9f0b4429b35 (patch) | |
tree | f8f5850ff05521ab82d65745894714a8796cbfb6 /lib/fixed-points.nix | |
parent | 030c5028b07afcedce7c5956015c629486cc79d9 (diff) | |
parent | 4c2d05dd6435d449a3651a6dd314d9411b5f8146 (diff) | |
download | nixpkgs-rootfs.tar nixpkgs-rootfs.tar.gz nixpkgs-rootfs.tar.bz2 nixpkgs-rootfs.tar.lz nixpkgs-rootfs.tar.xz nixpkgs-rootfs.tar.zst nixpkgs-rootfs.zip |
Signed-off-by: Alyssa Ross <hi@alyssa.is>
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 a63f349b713..3b5fdc9e8ea 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 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 - 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; |