unison-core1-0.0.0
Safe HaskellSafe-Inferred
LanguageHaskell2010

Unison.Util.Components

Synopsis

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