lib.fixedPoints: explicit recursion functions

lib.fixedPoints.fix

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.

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-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-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-repl> fix = f:
  let self = f self; in self;

By applying fix we get the final result.

nix-repl> fix f
{ bar = "bar"; foo = "foo"; foobar = "foobar"; }

Such a refactored f using fix is not useful by itself. See extends for an example use case. There self is also often called final.

Inputs

f

1. Function argument

Type

fix :: (a -> a) -> a

Examples

Example

lib.fixedPoints.fix usage 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 ]

Located at lib/fixed-points.nix:92 in <nixpkgs>.

lib.fixedPoints.fix'

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.

Inputs

f

1. Function argument

Type

fix' :: (a -> a) -> a

Located at lib/fixed-points.nix:118 in <nixpkgs>.

lib.fixedPoints.converge

Returns the fixpoint that f converges to when called iteratively, starting with the input x.

nix-repl> converge (x: x / 2) 16
0

Inputs

f

1. Function argument

x

2. Function argument

Type

converge :: (a -> a) -> a -> a

Located at lib/fixed-points.nix:152 in <nixpkgs>.

lib.fixedPoints.extends

Extend a function using an overlay.

Overlays allow modifying and extending fixed-point functions, specifically ones returning attribute sets. A fixed-point function is a function which is intended to be evaluated by passing the result of itself as the argument. This is possible due to Nix's lazy evaluation.

A fixed-point function returning an attribute set has the form

final: {
  # attributes
}

where final refers to the lazily evaluated attribute set returned by the fixed-point function.

An overlay to such a fixed-point function has the form

final: prev: {
  # attributes
}

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.

Applying an overlay is done with extends:

let
  f = final: {
    # attributes
  };
  overlay = final: prev: {
    # attributes
  };
in extends overlay f;

To get the value of final, use lib.fix:

let
  f = final: {
    # attributes
  };
  overlay = final: prev: {
    # attributes
  };
  g = extends overlay f;
in fix g

Note

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.

The given fixed-point function is called with a separate argument than if it was evaluated with lib.fix.

Example

Extend a fixed-point function with an overlay

Define a fixed-point function f that expects its own output as the argument final:

f = final: {
  # Constant value a
  a = 1;

  # b depends on the final value of a, available as final.a
  b = final.a + 2;
}

Evaluate this using lib.fix to get the final result:

fix f
=> { a = 1; b = 3; }

An overlay represents a modification or extension of such a fixed-point function. Here's an example of an overlay:

overlay = final: prev: {
  # Modify the previous value of a, available as prev.a
  a = prev.a + 10;

  # Extend the attribute set with c, letting it depend on the final values of a and b
  c = final.a + final.b;
}

Use extends overlay f to apply the overlay to the fixed-point function f. This produces a new fixed-point function g with the combined behavior of f and overlay:

g = extends overlay f

The result is a function, so we can't print it directly, but it's the same as:

g' = final: {
  # The constant from f, but changed with the overlay
  a = 1 + 10;

  # Unchanged from f
  b = final.a + 2;

  # Extended in the overlay
  c = final.a + final.b;
}

Evaluate this using lib.fix again to get the final result:

fix g
=> { a = 11; b = 13; c = 24; }

Inputs

overlay

The overlay to apply to the fixed-point function

f

The fixed-point function

Type

extends :: (AttrSet -> AttrSet -> AttrSet) # The overlay to apply to the fixed-point function
        -> (AttrSet -> AttrSet) # A fixed-point function
        -> (AttrSet -> AttrSet) # The resulting fixed-point function

Examples

Example

lib.fixedPoints.extends usage example

f = final: { a = 1; b = final.a + 2; }

fix f
=> { a = 1; b = 3; }

fix (extends (final: prev: { a = prev.a + 10; }) f)
=> { a = 11; b = 13; }

fix (extends (final: prev: { b = final.a + 5; }) f)
=> { a = 1; b = 6; }

fix (extends (final: prev: { c = final.a + final.b; }) f)
=> { a = 1; b = 3; c = 4; }

Located at lib/fixed-points.nix:325 in <nixpkgs>.

lib.fixedPoints.composeExtensions

Compose two overlay functions and return a single overlay function that combines them. For more details see: composeManyExtensions.

Located at lib/fixed-points.nix:340 in <nixpkgs>.

lib.fixedPoints.composeManyExtensions

Composes a list of overlays and returns a single overlay function that combines them.

Note

The result is produced by using the update operator //. This means nested values of previous overlays are not merged recursively. In other words, previously defined attributes are replaced, ignoring the previous value, unless referenced by the overlay; for example final: prev: { foo = final.foo + 1; }.

Inputs

extensions

Note

A list of overlay functions The order of the overlays in the list is important.

Each overlay function takes two arguments, by convention final and prev, and returns an attribute set.

  • final is the result of the fixed-point function, with all overlays applied.
  • prev is the result of the previous overlay function(s).

Type

# Pseudo code
let
  #               final      prev
  #                 ↓          ↓
  OverlayFn = { ... } -> { ... } -> { ... };
in
composeManyExtensions :: [OverlayFn] -> OverlayFn

Examples

Example

lib.fixedPoints.composeManyExtensions usage example

let
  # The "original function" that is extended by the overlays.
  # Note that it doesn't have prev: as argument since no overlay function precedes it.
  original = final: { a = 1; };

  # Each overlay function has 'final' and 'prev' as arguments.
  overlayA = final: prev: { b = final.c; c = 3; };
  overlayB = final: prev: { c = 10; x = prev.c or 5; };

  extensions = composeManyExtensions [ overlayA overlayB ];

  # Calculate the fixed point of all composed overlays.
  fixedpoint = lib.fix (lib.extends extensions original );

in fixedpoint
=>
{
  a = 1;
  b = 10;
  c = 10;
  x = 3;
}

Located at lib/fixed-points.nix:412 in <nixpkgs>.

lib.fixedPoints.makeExtensible

Create an overridable, recursive attribute set. For example:

nix-repl> obj = makeExtensible (final: { })

nix-repl> obj
{ __unfix__ = «lambda»; extend = «lambda»; }

nix-repl> obj = obj.extend (final: prev: { foo = "foo"; })

nix-repl> obj
{ __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }

nix-repl> obj = obj.extend (final: prev: { foo = prev.foo + " + "; bar = "bar"; foobar = final.foo + final.bar; })

nix-repl> obj
{ __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }

Located at lib/fixed-points.nix:434 in <nixpkgs>.

lib.fixedPoints.makeExtensibleWithCustomName

Same as makeExtensible but the name of the extending attribute is customized.

Inputs

extenderName

1. Function argument

rattrs

2. Function argument

Located at lib/fixed-points.nix:450 in <nixpkgs>.

lib.fixedPoints.toExtension

Convert to an extending function (overlay).

toExtension is the toFunction for extending functions (a.k.a. extensions or overlays). It converts a non-function or a single-argument function to an extending function, while returning a two-argument function as-is.

That is, it takes a value of the shape x, prev: x, or final: prev: x, and returns final: prev: x, assuming x is not a function.

This function takes care of the input to stdenv.mkDerivation's overrideAttrs function. It bridges the gap between <pkg>.overrideAttrs before and after the overlay-style support.

Inputs

f : The function or value to convert to an extending function.

Type

toExtension :: b' -> Any -> Any -> b'
or
toExtension :: (a -> b') -> Any -> a -> b'
or
toExtension :: (a -> a -> b) -> a -> a -> b
where b' = ! Callable

Set a = b = b' = AttrSet & ! Callable to make toExtension return an extending function.

Examples

Example

lib.fixedPoints.toExtension usage example

fix (final: { a = 0; c = final.a; })
=> { a = 0; c = 0; };

fix (extends (toExtension { a = 1; b = 2; }) (final: { a = 0; c = final.a; }))
=> { a = 1; b = 2; c = 1; };

fix (extends (toExtension (prev: { a = 1; b = prev.a; })) (final: { a = 0; c = final.a; }))
=> { a = 1; b = 0; c = 1; };

fix (extends (toExtension (final: prev: { a = 1; b = prev.a; c = final.a + 1 })) (final: { a = 0; c = final.a; }))
=> { a = 1; b = 0; c = 2; };

Located at lib/fixed-points.nix:512 in <nixpkgs>.