“Efficient” string builder in nix

string-builder.nix

let
  list =
    rec {

      empty = { a = null; cons = null; };
      singleton = x: { a = x; cons = null; };
      cons = x: xs: { a = x; cons = xs; };

      # O(n)
      foldr = f: zero:
        let go = {a, cons}:
          if cons == null
          then
            if a == null
            then zero
            else f a zero
          else f a (go cons);
        in go;

      # O(n) (length of xs)
      append = xs: ys: foldr cons ys xs;

      # O(n)
      strictArrayToList = builtins.foldl' (xs: x: append xs (singleton x)) empty;

      # O(n) (does it have to copy the array for every element? Probably)
      # TODO: might need a seq somewhere
      listToStrictArray = {a, cons}:
        if cons == null then
          if a == null
          then []
          else [a]
        else [a] ++ listToStrictArray cons;

    };

in {
  string = str: s: list.cons str s;
  append = b1: b2: s: b1 (b2 s);
  runBuilder = b1:
    builtins.concatStringsSep
      ""
      (list.listToStrictArray
        (b1 list.empty));
}