readDirRecursive.nix

let
  # traverse an item of type T topologically.
  # returns a List T
  topoTraverse =
    # T -> List T -- unfold an item into its next layer
    unfoldList:
    # T -> Bool -- whether to recurse further on an item
    pred:
    # T -- the start item
    tree:
    let
      work = unfoldList tree;
      moreWork = builtins.filter pred work;
    in work ++ lib.concatMap (topoTraverse unfoldList pred) moreWork;

  # builtins.readDir, but recurses into directories.
  # returns List { path, type }
  # where path is the full path of a file
  # and type is its type like returned from builtins.readDir
  readDirRecursively =
    # whether to recurse into a directory
    recurseDirPred:
    # the directory to read
    dir:
    topoTraverse
    # run builtins.readDir to get the next level
    (dir: lib.mapAttrsToList (basename: type: {
        path = (toString dir.path) + "/" + (toString basename);
        inherit type;
      })
      (builtins.readDir dir.path))
    # only recurse when it’s a directory and the predicate matches
    (x: x.type == "directory" && recurseDirPred x.path)
    # initial value
    { path = dir; type = "directory"; };


in {}