| Safe Haskell | None |
|---|---|
| Language | GHC2024 |
Tile.Tree
Description
trees.
The pipeline converts a Tiling into a Schedule through a
sequence of tree transformations:
decompositionTree→contractAnchors→hopTree→sendTree
The generic spine (Tree, unfoldTree, mapTree) is the common
substrate for all four views.
Synopsis
- data Tree a = Tree {}
- mapTree :: (a -> b) -> Tree a -> Tree b
- unfoldTree :: (a -> [a]) -> a -> Tree a
- treeLabels :: Ord a => Tree a -> Set a
- treeIndex :: Ord a => Tree a -> Map a (Tree a)
- renderTreeWith :: (a -> String) -> Tree a -> String
- data DecompositionView
- data HopView
- newtype TileTree (view :: k) = TileTree {}
- type DecompositionTree = TileTree DecompositionView
- type HopTree = TileTree HopView
- newtype SendTree = SendTree {
- getSendTree :: Tree Tile
- newtype RoutedTree a = RoutedTree {
- getRoutedTree :: Tree a
- decompositionTree :: Tiling t => t -> Tile -> DecompositionTree
- contractAnchors :: DecompositionTree -> HopTree
- hopTree :: Tiling t => t -> Tile -> HopTree
- sendTree :: Tiling t => t -> Tile -> SendTree
- children :: Tiling t => t -> Tile -> [Tile]
- scheduleTree :: Ord a => a -> Schedule a -> RoutedTree a
- routedTree :: Ord a => RoutedSchedule a -> RoutedTree a
- renderDecompositionTree :: [String] -> DecompositionTree -> String
- renderHopTree :: [String] -> HopTree -> String
- renderSendTree :: [String] -> SendTree -> String
- renderRoutedTree :: RoutedTree String -> String
Generic tree
A rose tree: a label with an ordered list of subtrees.
unfoldTree :: (a -> [a]) -> a -> Tree a Source #
Build a tree from a seed by repeatedly applying a child function.
renderTreeWith :: (a -> String) -> Tree a -> String Source #
Render a tree as an ASCII box-drawing string.
Tile tree views
data DecompositionView Source #
Phantom type distinguishing a structural decomposition tree.
newtype TileTree (view :: k) Source #
A tree of TileNodes tagged with a phantom view type to prevent
mixing structurally distinct tree views.
Constructors
| TileTree | |
Fields | |
type DecompositionTree = TileTree DecompositionView Source #
A structural decomposition tree: every node carries the full
Relation metadata from its parent split.
type HopTree = TileTree HopView Source #
A hop tree: anchor nodes have been contracted; every edge is a communication hop.
A tree of Tiles whose roots are the communication destinations.
Each parent–child edge corresponds to one Step in the fault-free
schedule.
Constructors
| SendTree | |
Fields
| |
newtype RoutedTree a Source #
A tree of schedule members reconstructed from a RoutedSchedule.
Constructors
| RoutedTree | |
Fields
| |
Instances
| Eq a => Eq (RoutedTree a) Source # | |
Defined in Tile.Tree | |
| Show a => Show (RoutedTree a) Source # | |
Defined in Tile.Tree Methods showsPrec :: Int -> RoutedTree a -> ShowS # show :: RoutedTree a -> String # showList :: [RoutedTree a] -> ShowS # | |
Tile pipeline
decompositionTree :: Tiling t => t -> Tile -> DecompositionTree Source #
Unfold the structural decomposition of a tile using childNodes.
Every node in the result carries its Relation to its parent.
contractAnchors :: DecompositionTree -> HopTree Source #
Convert a DecompositionTree into a HopTree by contracting
anchor edges. Anchor nodes are spliced out and their sibling
descendants promoted; the result contains only communication hops.
hopTree :: Tiling t => t -> Tile -> HopTree Source #
Build the hop tree for a tile: structural decomposition followed by anchor contraction.
hopTree = contractAnchors . decompositionTree
children :: Tiling t => t -> Tile -> [Tile] Source #
Direct communication children of a tile: the roots of the
subtiles in its SendTree.
Schedule trees
scheduleTree :: Ord a => a -> Schedule a -> RoutedTree a Source #
Reconstruct a broadcast tree from a schedule by following
sender-to-receiver edges in adjacencyList order.
routedTree :: Ord a => RoutedSchedule a -> RoutedTree a Source #
Build a RoutedTree from a RoutedSchedule.
Rendering
renderDecompositionTree :: [String] -> DecompositionTree -> String Source #
Render a DecompositionTree with numbered tile nodes.
renderHopTree :: [String] -> HopTree -> String Source #
Render a HopTree showing each tile's member set.
renderSendTree :: [String] -> SendTree -> String Source #
Render a SendTree showing each tile's communication root.
renderRoutedTree :: RoutedTree String -> String Source #
Render a RoutedTree of strings.