Documentation

treeIndexBase. Index of first element of |a tree tuple.

flattenTree tree. Flattens tree using a depth first traversal, |returning the list of its leaves.

treeLeaf takes a tree and if it is a leaf, returns it, or otherwise |throws the error message given.

alignTrees treeA treeB aligns treeA and treeB to produce |a mapping from treeA leaves to treeB nodes. If the trees |don't fit/have the same shape, then an error is thrown.

zipTrees treeA treeB. Assuming treeA is a subset of treeB |returns a new tree with all children in b dangling from those |in a. Throws error otherwise.

zipSubTrees treeA treeB. Returns a list of associated subtrees, for e.g. | zipSubTrees (Tup [Tup [Lf a, Lf b], Lf c]) (Tup [Lf x, Tup [Lf y, Lf z]]) = | [(Tup [Lf a, Lf b], Lf x), (Lf c, Tup [Lf y, Lf z])]. This will fail if two |tuples at the same level have different numbers of children, or if a tuple is |at the same level as a lambda etc.

visitTreeM visits the tree using a depth first traversal |and creates a new tree using the monadic function to transform |its leaf values.

mapTree f tree. Returns a tree where all leaf values have been transformed |using f.

mapTree f tree. Returns a tree where all leaf values have been transformed |using f.

treeToList takes a tree and returns a list of its elements |created using a depth first traversal

growTree smallTree largeTree newLeaf. Grows smallTree |to be the same size and shape of largeTree, by creating |new nodes with newLeaf.

lookupTreeNodeMaybe tree path. Looks up the node at path |in tree, or returns Nothing if doesn't exist.

lookupTreeNode errMsg tree path. Looks up the node at path |in tree, or throws an error if it does not exist.

lookupTreeNodeOrLeaf errMsg tree path. Follows the tree path, |to return either the node at the path, or a leaf, |whatever comes first.

replaceTreeNode path newNode oldTree. Returns oldTree where the node |at path has been replaced with newNode, or throws error if no such path |exists in oldTree.

subPaths pathList pathPrefix. Filters pathList returning only |those for which pathPrefix is a prefix. Note: Here first element |is root of tree.

createTreeFromPaths paths currentPathPrefix. Takes a list of tree paths, with labels and leaves |and builds them into a labelled tree.Note: head element of paths is root node in tree.

searchTree searchFun tree. Visits all leaves |returning a list of values generated by the searchFun.

filterTree pred tree. Accumulates all leaf values for which the |predicate pred holds.

treeContains pred tree. Returns true if tree contains |a leaf for which the predicate pred holds.

tidyTree tree. Pulls up tuples of length 1.

LabelledTree l v - a tree where every node has a label

flattenLTree tree. Flattens tree using a depth first |traversal, returning a list of its leaves and their labels.

treeLabel tree. Returns the label of a labelled tree.

labelledTreePath tree path. Looks up the node at path |in tree, or throws an error if it does not exist.

zipLabelledTrees treeA treeB. Assuming treeA is a subset of treeB |returns a new tree with all children in b dangling from those |in a. Throws error otherwise. Keeps labels from treeA.

toLabelledTree tree. Converts a tree to a labelled tree.

Converts from a labelled tree back to a normal |tree, disgarding the labels.

visitLabelledTreeM visits the tree using a depth first traversal |and creates a new tree using the monadic function to transform |its leaf values.

mapLabels f tree. Natural transformation of labelled tree labels.

createTreePathTree rootPath tree. Returns a tree with labels that are |tree paths for each node.

Contains vars instance for Tree

Data types

Contains vars instance for LfTy

isScalTy type. Returns if type is a |scalar type.

getVarTys lfTy. Returns the set of var ids in a leaf type.

mapGraphsInTy f ty. Applies f to all graphs in ty.

mapGraphsInTy f ty. Applies f to all graphs in ty.

returns list of all graphs in this type.

Scalar literals

scalValType val. Returns the type of this literal value.

Node ids

Node types

DFG nodes

Map from node ids to objects

looks up a member from a node environment or throws an |error with the given message

lookupNodeMaybe nodeId nodeEnv. Looks up the node, or |returns Nothing if it could not be found.

duplicateNodeEnvIds newIds oldEnv. Duplicates all entries in oldEnv |that exist in newIds, giving them the new ids defined in newIds, and then |returns all the original entries, and these new duplicated ones.

buildNodeTree graph nodeId type. Takes a graph and a node, and returns a |node tree of all its neighbours node ids. However this tree now also contains |leaves that access tuple values within a given node, which are identified |by treepaths.

buildInputNodeTree graph node. Builds a node tree from the input nodes |of a node.

If node is a TupAccNode and it's input is a TupNd, shortcuts them |to immediately get the original node.

buildOutputNodeTree takes a node, and looks through all its outputs |for tuple accessors, creating a labelled tree of output nodes.

Returns all graphs in a type env.

extendTyTree nodeId typeTree. Converts type tree into a tree of labels |for paths into it.

extendNodeTreeWithType tree type. Align tree with the |type and expand any leaves of tree that have tuple type |to provide leaves to access each of the tuple parts.

showSubgraphs g. Shows g and all the subgraphs nested in FunNds.

newGraph creates a new graph from a list of nodes

Sequentially compose graphs so g2 is applied after g1.

graphsContain graph nodeId. Returns true if one of the graphs |contains a node with id nodeId.

findInGraph nodeTy graph. Searches graph for |nodes with nodeTy and returns a list of all the nodes |that do.

lookupGraphNodeMaybe nid graph. Searches up graphs, |checking the current graph, and if it doesn't contain it |checking it's parent.

lookupGraphVarNode msg node allGraphs graphs. If node is a varNode called |something other than in or out, then this function searches up the |graph stack for a node bound to that name. If one exists, it then searches |from the leaf graph up to the root again (using allGraphs) to find this node, |returning it if it is found, or throwing an error otherwise.

lookupNodeLeafGraph errMsg nid graph. If in leaf graph, returns it. |If in parent graphs, returns Nothing. If in none of them, throws error.

maxNodeId graph. Finds the maximum node id |in the graph, grahp's parents, and all fun nodes of that graph.

replaceNodeIds newNidMap graph. Returns a copy of the graph, |with the node ids replaced with the new ones in newNidMap.

removeParentNodes parNodes graph. Removes all nodes with |id's that exist in parNodes from graph. Also removes all |nodes with ids in parNodes or graph, from all graphs nested |in FunNd in graph.

gets the nodes from node ids for a given graph

getNodeCons graph prevNodeId curNodeId tupPaths. Recursively looks at node |outputs to find all consumers of the value identified by the |current node and tuple paths (which identify the relevant |subvalues of the current node's value). Returns a set of |all tup and tup acc that proceed the consumers, and the set of |consumers themselves.

getConsumers graph nodeId. Searches through all outputs, |and tuple, and tuple accessor nodes, finding consumers of the |value produced by this node. Returns a set of the nodes that |proceed these consumer nodes (and so may receive |values from the consumers), and the node ids of the consumer |nodes themselves.

visitNodeM f graph nodeId. if the node specified by nodeId has not already been visited |visits all its inputs, and then applies f to itself.

visitGraphM visitF graph. Depth first traversal of a graph, applying |visitF to each node, never visiting the same node twice.

maxDepthVisitor graph node. Records the maximum depth of this node in |the state. I.e. the number of nodes above it's deepest input.

visitDeepestNodeM pf f graph depths nodeId. if the node specified by nodeId has not already been visited |visits all its inputs, in order of descending depth, and then applies f to itself. |Uses pf to partition node lists into different groups, where the groups should be visited |in the order they appear in the list, but where members of groups can appear in any order.

cycleVisitor checks there are no cycles in our graph.

visitDeepestGraphM visitF graph. Visits the nodes in the graph in deepest |first depth first traversal. I.e. it visits the deepest leaves, before shallower |ones.