| Safe Haskell | None |
|---|
LogicGrowsOnTrees.Path
Contents
Description
This modules contains functionality relating to paths through trees.
- data BranchChoice
- data Step
- type Path = Seq Step
- oppositeBranchChoiceOf :: BranchChoice -> BranchChoice
- sendTreeDownPath :: Path -> Tree α -> Tree α
- sendTreeTDownPath :: Monad m => Path -> TreeT m α -> m (TreeT m α)
- data WalkError
Types
data BranchChoice Source
A choice at a branch point to take either the left branch or the right branch.
Constructors
| LeftBranch | |
| RightBranch |
A step in a path through a tree, which can either pass through a point with a cached result or take a choice to go left or right at a branch point.
Constructors
| CacheStep ByteString | Step through a cache point |
| ChoiceStep BranchChoice | Step through a choice point |
Functions
oppositeBranchChoiceOf :: BranchChoice -> BranchChoiceSource
Returns the opposite of the given branch choice.
sendTreeDownPath :: Path -> Tree α -> Tree αSource
Follows a Path through a Tree to a particular subtree; the
main use case of this function is for a processor which has been given a
particular subtree as its workload to zoom in on that subtree. The way this
function works is as follows: as long as the remaining path is non-empty, it
explores the Tree until it encounters either a cache point or a choice
point; in the former case the path supplies the cached value in the
CacheStep constructor, and in the latter case the path supplies the branch
to take in the ChoiceStep constructor; when the remaining path is empty
then the resulting Tree is returned.
WARNING: This function is not valid for all inputs; it makes the
assumption that the given Path has been derived from the given Tree so
that the path will always encountered choice points exactly when the tree
does and likewise for cache points. Furthermore, the path must not run out
before the tree hits a leaf. If any of these conditions is violated, a
WalkError exception will be thrown; in fact, you should hope than
exception is thrown because it will let you know that there is a bug your
code as the alternative is that you accidently give it a path that is not
derived from the given tree but which coincidentally matches it which means
that it will silently return a nonsensical result. Having said all that, you
should almost never need to worry about this possibility in practice because
there will normally be only one tree in use at a time and all paths in use
will have come from that tree.
sendTreeTDownPath :: Monad m => Path -> TreeT m α -> m (TreeT m α)Source
Like sendTreeDownPath, but for impure trees.
Exceptions
This exception is thrown whenever a Tree is sent down a path which
is incompatible with it.
Constructors
| TreeEndedBeforeEndOfWalk | Indicates that a path is too long for a given tree --- that is, the walk hit a leaf (or a null) before the end of the path was reached. |
| PastTreeIsInconsistentWithPresentTree | Indicates that a choice step in a path coincided with a cache point in a tree, or vice versa. |