lib: Move fixed-point combinators out of trivial

Trivia != prelude. This is a better organized and less likely to
scare off new contributors.

3 files changed, 83 insertions, 81 deletions

diff --git a/lib/default.nix b/lib/default.nix
index e692637abf1..3893e349db3 100644
--- a/lib/default.nix
+++ b/lib/default.nix
@@ -5,8 +5,9 @@
  */
 let
 
-  # trivial, often used functions
+  # often used, or depending on very little
   trivial = import ./trivial.nix;
+  fixedPoints = import ./fixed-points.nix;
 
   # datatypes
   attrsets = import ./attrsets.nix;
@@ -42,7 +43,7 @@ let
   filesystem = import ./filesystem.nix;
 
 in
-  { inherit trivial
+  { inherit trivial fixedPoints
             attrsets lists strings stringsWithDeps
             customisation maintainers meta sources
             modules options types
@@ -55,6 +56,7 @@ in
   }
   # !!! don't include everything at top-level; perhaps only the most
   # commonly used functions.
-  // trivial // lists // strings // stringsWithDeps // attrsets // sources
+  // trivial // fixedPoints
+  // lists // strings // stringsWithDeps // attrsets // sources
   // options // types // meta // debug // misc // modules
   // customisation
diff --git a/lib/fixed-points.nix b/lib/fixed-points.nix
new file mode 100644
index 00000000000..a11b5a6f4bd
--- /dev/null
+++ b/lib/fixed-points.nix
@@ -0,0 +1,78 @@
+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:
+  #
+  #     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:
+  #
+  #     nix-repl> fix f
+  #     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
+  #
+  #  Type: fix :: (a -> a) -> a
+  #
+  # See https://en.wikipedia.org/wiki/Fixed-point_combinator for further
+  # details.
+  fix = f: let x = f x; in x;
+
+  # A variant of `fix` that records the original recursive attribute set in the
+  # result. This is useful in combination with the `extends` function to
+  # implement deep overriding. See pkgs/development/haskell-modules/default.nix
+  # for a concrete example.
+  fix' = f: let x = f x // { __unfix__ = f; }; in x;
+
+  # Modify the contents of an explicitly recursive attribute set in a way that
+  # honors `self`-references. This is accomplished with a function
+  #
+  #     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.
+  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: self: super:
+      let fApplied = f self super;
+          super' = super // fApplied;
+      in fApplied // g self super';
+
+  # 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' rattrs // {
+      ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
+   };
+}
diff --git a/lib/trivial.nix b/lib/trivial.nix
index ffbf96aa9bc..9ee0549fc0f 100644
--- a/lib/trivial.nix
+++ b/lib/trivial.nix
@@ -43,84 +43,6 @@ rec {
   */
   mergeAttrs = x: y: x // y;
 
-
-  # 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:
-  #
-  #     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:
-  #
-  #     nix-repl> fix f
-  #     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
-  #
-  #  Type: fix :: (a -> a) -> a
-  #
-  # See https://en.wikipedia.org/wiki/Fixed-point_combinator for further
-  # details.
-  fix = f: let x = f x; in x;
-
-  # A variant of `fix` that records the original recursive attribute set in the
-  # result. This is useful in combination with the `extends` function to
-  # implement deep overriding. See pkgs/development/haskell-modules/default.nix
-  # for a concrete example.
-  fix' = f: let x = f x // { __unfix__ = f; }; in x;
-
-  # Modify the contents of an explicitly recursive attribute set in a way that
-  # honors `self`-references. This is accomplished with a function
-  #
-  #     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.
-  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: self: super:
-      let fApplied = f self super;
-          super' = super // fApplied;
-      in fApplied // g self super';
-
-  # 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' rattrs // {
-      ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
-   };
-
   # Flip the order of the arguments of a binary function.
   flip = f: a: b: f b a;