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
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);