1 files changed, 257 insertions, 0 deletions
diff --git a/users/sterni/nix/fun/default.nix b/users/sterni/nix/fun/default.nix
new file mode 100644
index 000000000000..bb10f9e6c1bf
--- /dev/null
+++ b/users/sterni/nix/fun/default.nix
@@ -0,0 +1,257 @@
+{ depot, lib, ... }:
+
+let
+
+  inherit (lib)
+    id
+    ;
+
+  # Simple function composition,
+  # application is right to left.
+  rl = f1: f2:
+    (x: f1 (f2 x));
+
+  # Compose a list of functions,
+  # application is right to left.
+  rls = fs:
+    builtins.foldl' (fOut: f: lr f fOut) id fs;
+
+  # Simple function composition,
+  # application is left to right.
+  lr = f1: f2:
+    (x: f2 (f1 x));
+
+  # Compose a list of functions,
+  # application is left to right
+  lrs = x: fs:
+    builtins.foldl' (v: f: f v) x fs;
+
+  # Warning: cursed function
+  #
+  # Check if a function has an attribute
+  # set pattern with an ellipsis as its argument.
+  #
+  # s/o to puck for discovering that you could use
+  # builtins.toXML to introspect functions more than
+  # you should be able to in Nix.
+  hasEllipsis = f:
+    builtins.isFunction f &&
+    builtins.match ".*<attrspat ellipsis=\"1\">.*"
+      (builtins.toXML f) != null;
+
+  /* Return the number of arguments the given function accepts or 0 if the value
+     is not a function.
+
+     Example:
+
+       argCount argCount
+       => 1
+
+       argCount builtins.add
+       => 2
+
+       argCount pkgs.stdenv.mkDerivation
+       => 1
+  */
+  argCount = f:
+    let
+      # N.B. since we are only interested if the result of calling is a function
+      # as opposed to a normal value or evaluation failure, we never need to
+      # check success, as value will be false (i.e. not a function) in the
+      # failure case.
+      called = builtins.tryEval (
+        f (builtins.throw "You should never see this error message")
+      );
+    in
+    if !(builtins.isFunction f || builtins.isFunction (f.__functor or null))
+    then 0
+    else 1 + argCount called.value;
+
+  /* Call a given function with a given list of arguments.
+
+     Example:
+
+       apply builtins.sub [ 20 10 ]
+       => 10
+  */
+  apply = f: args:
+    builtins.foldl' (f: x: f x) f args;
+
+  # TODO(sterni): think of a better name for unapply
+  /* Collect n arguments into a list and pass them to the given function.
+     Allows calling a function that expects a list by feeding it the list
+     elements individually as function arguments - the limitation is
+     that the list must be of constant length.
+
+     This is mainly useful for functions that wrap other, arbitrary functions
+     in conjunction with argCount and apply, since lists of arguments are
+     easier to deal with usually.
+
+     Example:
+
+       (unapply 3 lib.id) 1 2 3
+       => [ 1 2 3 ]
+
+       (unapply 5 lib.reverse) 1 2 null 4 5
+       => [ 5 4 null 2 1 ]
+
+       # unapply and apply compose the identity relation together
+
+       unapply (argCount f) (apply f)
+       # is equivalent to f (if the function has a constant number of arguments)
+
+       (unapply 2 (apply builtins.sub)) 20 10
+       => 10
+  */
+  unapply =
+    let
+      unapply' = acc: n: f: x:
+        if n == 1
+        then f (acc ++ [ x ])
+        else unapply' (acc ++ [ x ]) (n - 1) f;
+    in
+    unapply' [ ];
+
+  /* Optimize a tail recursive Nix function by intercepting the recursive
+     function application and expressing it in terms of builtins.genericClosure
+     instead. The main benefit of this optimization is that even a naively
+     written recursive algorithm won't overflow the stack.
+
+     For this to work the following things prerequisites are necessary:
+
+     - The passed function needs to be a fix point for its self reference,
+       i. e. the argument to tailCallOpt needs to be of the form
+       `self: # function body that uses self to call itself`.
+       This is because tailCallOpt needs to manipulate the call to self
+       which otherwise wouldn't be possible due to Nix's lexical scoping.
+
+     - The passed function may only call itself as a tail call, all other
+       forms of recursions will fail evaluation.
+
+     This function was mainly written to prove that builtins.genericClosure
+     can be used to express any (tail) recursive algorithm. It can be used
+     to avoid stack overflows for deeply recursive, but naively written
+     functions (in the context of Nix this mainly means using recursion
+     instead of (ab)using more performant and less limited builtins).
+     A better alternative to using this function is probably translating
+     the algorithm to builtins.genericClosure manually. Also note that
+     using tailCallOpt doesn't mean that the stack won't ever overflow:
+     Data structures, especially lazy ones, can still cause all the
+     available stack space to be consumed.
+
+     The optimization also only concerns avoiding stack overflows,
+     tailCallOpt will make functions slower if anything.
+
+     Type: (F -> F) -> F where F is any tail recursive function.
+
+     Example:
+
+     let
+       label' = self: acc: n:
+         if n == 0
+         then "This is " + acc + "cursed."
+         else self (acc + "very ") (n - 1);
+
+       # Equivalent to a naive recursive implementation in Nix
+       label = (lib.fix label') "";
+
+       labelOpt = (tailCallOpt label') "";
+     in
+
+     label 5
+     => "This is very very very very very cursed."
+
+     labelOpt 5
+     => "This is very very very very very cursed."
+
+     label 10000
+     => error: stack overflow (possible infinite recursion)
+
+     labelOpt 10000
+     => "This is very very very very very very very very very…
+  */
+  tailCallOpt = f:
+    let
+      argc = argCount (lib.fix f);
+
+      # This function simulates being f for f's self reference. Instead of
+      # recursing, it will just return the arguments received as a specially
+      # tagged set, so the recursion step can be performed later.
+      fakef = unapply argc (args: {
+        __tailCall = true;
+        inherit args;
+      });
+      # Pass fakef to f so that it'll be called instead of recursing, ensuring
+      # only one recursion step is performed at a time.
+      encodedf = f fakef;
+
+      opt = args:
+        let
+          steps = builtins.genericClosure {
+            # This is how we encode a (tail) call: A set with final == false
+            # and the list of arguments to pass to be found in args.
+            startSet = [
+              {
+                key = "0";
+                id = 0;
+                final = false;
+                inherit args;
+              }
+            ];
+
+            operator =
+              { id, final, ... }@state:
+              let
+                # Plumbing to make genericClosure happy
+                newIds = {
+                  key = toString (id + 1);
+                  id = id + 1;
+                };
+
+                # Perform recursion step
+                call = apply encodedf state.args;
+
+                # If call encodes a new call, return the new encoded call,
+                # otherwise signal that we're done.
+                newState =
+                  if builtins.isAttrs call && call.__tailCall or false
+                  then newIds // {
+                    final = false;
+                    inherit (call) args;
+                  } else newIds // {
+                    final = true;
+                    value = call;
+                  };
+              in
+
+              if final
+              then [ ] # end condition for genericClosure
+              else [ newState ];
+          };
+        in
+        # The returned list contains intermediate steps we ignore.
+        (builtins.head (builtins.filter (x: x.final) steps)).value;
+    in
+    unapply argc opt;
+in
+
+{
+  inherit (lib)
+    fix
+    flip
+    const
+    ;
+
+  inherit
+    id
+    rl
+    rls
+    lr
+    lrs
+    hasEllipsis
+    argCount
+    tailCallOpt
+    apply
+    unapply
+    ;
+}