Skip to content

Instantly share code, notes, and snippets.

@Profpatsch
Created November 19, 2022 19:21
Show Gist options
  • Save Profpatsch/afb8018c504a5c775446800bb13b0eaa to your computer and use it in GitHub Desktop.
Save Profpatsch/afb8018c504a5c775446800bb13b0eaa to your computer and use it in GitHub Desktop.
“Efficient” string builder in 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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment