listDfs

lib.lists.listDfs

Docs pulled from | This Revision | 10 minutes ago

Depth-First Search (DFS) for lists list != [].

before a b == true means that b depends on a (there's an edge from b to a).

Inputs

stopOnCycles: 1. Function argument
before: 2. Function argument
list: 3. Function argument

Examples

`lib.lists.listDfs` usage example

listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
  == { minimal = "/";                  # minimal element
       visited = [ "/home/user" ];     # seen elements (in reverse order)
       rest    = [ "/home" "other" ];  # everything else
     }

listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
  == { cycle   = "/";                  # cycle encountered at this element
       loops   = [ "/" ];              # and continues to these elements
       visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
       rest    = [ "/home" "other" ];  # everything else

Noogle detected

Aliases

lib.listDfs

Implementation

The following is the current implementation of this function.

listDfs =
    stopOnCycles: before: list:
    let
      dfs' =
        us: visited: rest:
        let
          c = filter (x: before x us) visited;
          b = partition (x: before x us) rest;
        in
        if stopOnCycles && (length c > 0) then
          {
            cycle = us;
            loops = c;
            inherit visited rest;
          }
        else if length b.right == 0 then
          # nothing is before us
          {
            minimal = us;
            inherit visited rest;
          }
        else
          # grab the first one before us and continue
          dfs' (head b.right) ([ us ] ++ visited) (tail b.right ++ b.wrong);
    in
    dfs' (head list) [ ] (tail list);