Basic functionality for building and exploring trees.

The following are the tree types that are accepted by most of the functions in this package. You do not need to know the details of their definitions unless you intend to write your own custom routines for running and transforming trees, in which case the relevant information is at the bottom of this page in the Implementation section.

There is one type of pure tree and two types of impure trees. In general, your tree should nearly always be pure if you are planning to make use of checkpointing or parallel exploring, as parts of the tree may be explored multiple times, some parts may not be run at all on a given processor, and whenever a leaf is hit there will be a jump to a higher node, so if your tree is impure then the result needs to not depend on how the tree is explored; an example of an acceptable use of an inner monad is when you want to memoize a pure function using a stateful monad.

If you need something like state in your tree, then you should consider nesting the tree monad in the state monad rather than vice-versa, because this will do things like automatically erasing the change in state that happened between an inner node and a leaf when the tree jumps back up from the leaf to an inner node, which will usually be what you want.

Trees are instances of MonadExplorable and MonadExplorableTrans, which are both subclasses of MonadPlus. The additional functionality offered by these type-classes is the ability to cache results so that a computation does not need to be repeated when a node is explored a second time, which can happen either when resuming from a checkpoint or when a workload has been stolen by another processor, as the first step is to retrace the path through the tree that leads to the stolen workload.

These features could have been provided as functions, but there are two reasons why they were subsumed into type-classes: first, because one might want to add another layer above the Tree monad transformers in the monad stack (as is the case in LogicGrowsOnTrees.Location), and second, because one might want to run a tree using a simpler monad such as List for testing purposes.

NOTE: Caching a computation takes space in the Checkpoint, so it is something you should only do when the result is relatively small and the computation is very expensive and is high enough in the search tree that it is likely to be repeated often. If the calculation is low enough in the search tree that it is unlikely to be repeated, is cheap enough so that repeating it is not a big deal, or produces a result with an incredibly large memory footprint, then you are probably better off not caching the result.

There are three kinds of functions in this module: functions that explore trees in various ways, functions that make it easier to build trees, and a function that changes the base monad of a pure tree.

The following functions all take a tree as input and produce the result of exploring it as output. There are seven functions because there are two kinds of trees --- pure and impure --- and three ways of exploring a tree --- exploring everything and summing all results (i.e., in the leaves), exploring until the first result (i.e., in a leaf) is encountered and immediately returning, and gathering results (i.e., from the leaves) until they satisfy a condition and then returning --- plus a seventh function that explores a tree only for the side-effects.

The following functions all create a tree from various inputs.

The implementation of the Tree types uses the approach described in "The Operational Monad Tutorial", published in Issue 15 of The Monad.Reader; specifically it uses the operational package. The idea is that a list of instructions are provided in TreeTInstruction, and then the operational monad does all the heavy lifting of turning them into a monad.