The intuition behind a hierarchy is that individuals may form groups, and groups may form groups, but no group can have zero individuals under its umbrella.
There are two main ways hierarchies can form (beyond just being an individual).
- Two or more groups can merge together (conjoin), forming one group where there were many before.
- Two or more groups can join up underneath a new group, forming n+1 groups where there were n before.
These are the intuitions behind the two relations that hierarchies support.
- class Hierarchy h p where
- getPos :: h p a -> p
- individual :: p -> a -> h p a
- adjoin :: p -> h p a -> h p a -> h p a
- adjoinsl :: p -> h p a -> [h p a] -> h p a
- adjoinsr :: p -> [h p a] -> h p a -> h p a
- adjoins :: p -> [h p a] -> h p a
- conjoin :: p -> h p a -> h p a -> h p a
- conjoinsl :: p -> h p a -> [h p a] -> h p a
- conjoinsr :: p -> [h p a] -> h p a -> h p a
- conjoins :: p -> [h p a] -> h p a
- class Openable f where
- type OpenAp f a = (a -> a, [f a] -> [f a])
- adjoinPos :: Hierarchy h p => h p a -> h p a -> h p a
- adjoinslPos :: Hierarchy h p => h p a -> [h p a] -> h p a
- adjoinsrPos :: Hierarchy h p => [h p a] -> h p a -> h p a
- adjoinsPos :: Hierarchy h p => [h p a] -> h p a
- conjoinPos :: Hierarchy h p => h p a -> h p a -> h p a
- conjoinslPos :: Hierarchy h p => h p a -> [h p a] -> h p a
- conjoinsrPos :: Hierarchy h p => [h p a] -> h p a -> h p a
- conjoinsPos :: Hierarchy h p => [h p a] -> h p a
A hierarchy is a set, together with an associative operation and a non-associative operation, as well as a duality law, which we'll get to after introducing the notation.
Although we also provide for source positions, we will omit them for simplicity in this description.
Ideally, I'd call the associative operation
<>, but the cool infix operators are
spoken for already, so I'll have to go with descriptive names.
Raising items into the hierarchy is done with
We call the associative operation
and the non-associative
In fact, there are two adjoins,
adjoinsr. Offering only these means we can
satisfy the invariant that groups recursively have at least one individual. In the discussions
below, assume that
adjoins is of type
[f a] -> [f a] -> f a, and that when called, at least
one of the arguments is non-empty.
The names literally mean "join together" and "join to", which succinctly convey the associativity properties of each. Well, "join to" might seem non-specific, but consider building a house in the wrong order as opposed to joining several cups of water in the wrong order. "Ad-" and "con-" have these meanings, even if the prepositions I've used as translation aren't so fine-grained.
The duality law is:
Some hierarchies may be commutative in conjoin and/or adjoin. For example, file systems
(ignoring links) are hierarchies: adjoin creates new directories (though it is not
the only way), and
conjoin adds files/directories into an existing directory, or creates a
new two-element directory. Clearly, conjoin is commutative here. For generality, we have
given default implemetations assuming non-commutativity in both operations.
It is often useful to look at the elements of a node in a
some transformation, then package the result back up as it was originally. Openable
provides exactly the required functionality. This may be useful more generally as
well, so we provide it as an independent class that can operate on structures that
have leaves and/or branches.
The minimal complete implementation is
Open a node, perform either the leaf or branch transform and close it back up.
Perform a preorder traversal version of
Perform a postorder traversal version of
Package a transformations for leaves and branches together.