lib/fixed-points.nix

   1 { lib, ... }:
   2 rec {
   3   # Compute the fixed point of the given function `f`, which is usually an
   4   # attribute set that expects its final, non-recursive representation as an
   5   # argument:
   6   #
   7   #     f = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }
   8   #
   9   # Nix evaluates this recursion until all references to `self` have been
  10   # resolved. At that point, the final result is returned and `f x = x` holds:
  11   #
  12   #     nix-repl> fix f
  13   #     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  14   #
  15   #  Type: fix :: (a -> a) -> a
  16   #
  17   # See https://en.wikipedia.org/wiki/Fixed-point_combinator for further
  18   # details.
  19   fix = f: let x = f x; in x;
  20
  21   # A variant of `fix` that records the original recursive attribute set in the
  22   # result. This is useful in combination with the `extends` function to
  23   # implement deep overriding. See pkgs/development/haskell-modules/default.nix
  24   # for a concrete example.
  25   fix' = f: let x = f x // { __unfix__ = f; }; in x;
  26
  27   # Return the fixpoint that `f` converges to when called recursively, starting
  28   # with the input `x`.
  29   #
  30   #     nix-repl> converge (x: x / 2) 16
  31   #     0
  32   converge = f: x:
  33     let
  34       x' = f x;
  35     in
  36       if x' == x
  37       then x
  38       else converge f x';
  39
  40   # Modify the contents of an explicitly recursive attribute set in a way that
  41   # honors `self`-references. This is accomplished with a function
  42   #
  43   #     g = self: super: { foo = super.foo + " + "; }
  44   #
  45   # that has access to the unmodified input (`super`) as well as the final
  46   # non-recursive representation of the attribute set (`self`). `extends`
  47   # differs from the native `//` operator insofar as that it's applied *before*
  48   # references to `self` are resolved:
  49   #
  50   #     nix-repl> fix (extends g f)
  51   #     { bar = "bar"; foo = "foo + "; foobar = "foo + bar"; }
  52   #
  53   # The name of the function is inspired by object-oriented inheritance, i.e.
  54   # think of it as an infix operator `g extends f` that mimics the syntax from
  55   # Java. It may seem counter-intuitive to have the "base class" as the second
  56   # argument, but it's nice this way if several uses of `extends` are cascaded.
  57   #
  58   # To get a better understanding how `extends` turns a function with a fix
  59   # point (the package set we start with) into a new function with a different fix
  60   # point (the desired packages set) lets just see, how `extends g f`
  61   # unfolds with `g` and `f` defined above:
  62   #
  63   # extends g f = self: let super = f self; in super // g self super;
  64   #             = self: let super = { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }; in super // g self super
  65   #             = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // g self { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; }
  66   #             = self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; } // { foo = "foo" + " + "; }
  67   #             = self: { foo = "foo + "; bar = "bar"; foobar = self.foo + self.bar; }
  68   #
  69   extends = f: rattrs: self: let super = rattrs self; in super // f self super;
  70
  71   # Compose two extending functions of the type expected by 'extends'
  72   # into one where changes made in the first are available in the
  73   # 'super' of the second
  74   composeExtensions =
  75     f: g: final: prev:
  76       let fApplied = f final prev;
  77           prev' = prev // fApplied;
  78       in fApplied // g final prev';
  79
  80   # Compose several extending functions of the type expected by 'extends' into
  81   # one where changes made in preceding functions are made available to
  82   # subsequent ones.
  83   #
  84   # composeManyExtensions : [packageSet -> packageSet -> packageSet] -> packageSet -> packageSet -> packageSet
  85   #                          ^final        ^prev         ^overrides     ^final        ^prev         ^overrides
  86   composeManyExtensions =
  87     lib.foldr (x: y: composeExtensions x y) (final: prev: {});
  88
  89   # Create an overridable, recursive attribute set. For example:
  90   #
  91   #     nix-repl> obj = makeExtensible (self: { })
  92   #
  93   #     nix-repl> obj
  94   #     { __unfix__ = «lambda»; extend = «lambda»; }
  95   #
  96   #     nix-repl> obj = obj.extend (self: super: { foo = "foo"; })
  97   #
  98   #     nix-repl> obj
  99   #     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 100   #
 101   #     nix-repl> obj = obj.extend (self: super: { foo = super.foo + " + "; bar = "bar"; foobar = self.foo + self.bar; })
 102   #
 103   #     nix-repl> obj
 104   #     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 105   makeExtensible = makeExtensibleWithCustomName "extend";
 106
 107   # Same as `makeExtensible` but the name of the extending attribute is
 108   # customized.
 109   makeExtensibleWithCustomName = extenderName: rattrs:
 110     fix' rattrs // {
 111       ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 112    };
 113 }