listDfs

lib.lists.listDfs

Docs pulled from | This Revision | about 1 hour 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);