Next iteration of bananas & barbed wire

recursive.nix

with import <nixpkgs> {};

let
  Recursive = { fmap, project }: {
    cata = alg:
      let c = val: alg (fmap c (project val));
      in c;
  };

  matchDef = def: matcher: v:
    let case = builtins.head (builtins.attrNames v);
    in (matcher.${case} or (def case)) v.${case};

  matchDefMap = def: matcher: v:
    let case = builtins.head (builtins.attrNames v);
    in { ${case} = (matcher.${case} or def) v.${case}; };

  nixRec = Recursive {
    project = v: { "${builtins.typeOf v}" = v; };
    fmap = f: matchDefMap lib.id {
      "set"  = lib.mapAttrs (lib.const f);
      "list" = map f;
    };
  };

in with lib;
nixRec.cata (matchDef
  (n: _: "(${n}?)!")
  {
    int = const "INT";
    set = a: lib.concatStringsSep ", " (mapAttrsToList (const id) a);
    list = concatStringsSep ", ";
  })
{ a = "bla"; b = [ 4 5 "foo" lib.id ]; }

# nix-instantiate ./test.nix --eval --strict --show-trace
# "(string?)!, INT, INT, (string?)!, (lambda?)!"