Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Synopsis
- components :: Ord v => (t -> Set v) -> [(v, t)] -> [[(v, t)]]
Documentation
components :: Ord v => (t -> Set v) -> [(v, t)] -> [[(v, t)]] Source #
Order bindings by dependencies and group into components. Each component consists of > 1 bindings, each of which depends transitively on all other bindings in the component.
1-element components may or may not depend on themselves.
The order is such that a component at index i will not depend on components and indexes > i. But a component at index i does not _necessarily_ depend on any components at earlier indices.
Example:
let rec ping n = pong (n + 1); pong n = ping (n + 1); g = id 42; y = id "hi" id x = x; in ping g
components
would produce `[[ping,pong], [id], [g], [y]]`
Notice that id
comes before g
and y
in the output, since
both g
and y
depend on id
.
Uses Tarjan's algorithm: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm