constant time append in nix

appendable.nix

{ lib, ... }:

let

  goodAttrByPath = p: v:
    builtins.foldl' (set: attr: let res = set."${attr}"; in res) v p;

  seqAttrs = attrs:
    let
      evalAttrs = builtins.foldl'
        (x: a: builtins.seq x attrs."${a}")
        null
        (builtins.attrNames attrs);
    in builtins.seq evalAttrs attrs;

  empty = {};

  size = a: a.size or 0;

  append = a: v:
    let
      new = {
        size = 1 + size a;
        previous = a;
        value = v;
      };
    in seqAttrs new;

  get = i: a:
    let
      depth = size a - (i + 1);
      path = builtins.genList
        (j:
          if j == depth
          then "value"
          else "previous") (depth + 1);
    in
      builtins.trace (toString i) (goodAttrByPath path a);

  toList = a:
    builtins.genList (lib.flip get a) (size a);

in {
  inherit
    empty
    append
    toList
    ;
}