Safe Haskell | Safe-Inferred |
---|

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

# Documentation

class Hierarchy h p whereSource

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 `++`

or `<>`

, 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 `individual`

.
We call the associative operation `conjoin`

and the non-associative `adjoins`

.

In fact, there are two adjoins, `adjoinsl`

and `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:

a`conjoin`

(b`adjoin`

c) === (a`adjoin`

b)`conjoin`

c

The minimal implementation is `individual`

, `conjoin`

, and `adjoinsl`

.

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.

individual :: p -> a -> h p aSource

adjoin :: p -> h p a -> h p a -> h p aSource

adjoinsl :: p -> h p a -> [h p a] -> h p aSource

adjoinsr :: p -> [h p a] -> h p a -> h p aSource

adjoins :: p -> [h p a] -> h p aSource

conjoin :: p -> h p a -> h p a -> h p aSource

conjoinsl :: p -> h p a -> [h p a] -> h p aSource

It is often useful to look at the elements of a node in a `Hierarchy`

, perform
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 `openAp`

.

openAp :: OpenAp f a -> f a -> f aSource

Open a node, perform either the leaf or branch transform and close it back up.

This algorithm should not recursively traverse the structure. Thus, even if the
structure consists only of leaves, `openAp`

is *not* a fancy way to say `fmap`

.

preorder :: OpenAp f a -> f a -> f aSource

Perform a preorder traversal version of `openAp`

.

postorder :: OpenAp f a -> f a -> f aSource

Perform a postorder traversal version of `openAp`

.

type OpenAp f a = (a -> a, [f a] -> [f a])Source

Package a transformations for leaves and branches together.

adjoinslPos :: Hierarchy h p => h p a -> [h p a] -> h p aSource

adjoinsrPos :: Hierarchy h p => [h p a] -> h p a -> h p aSource

adjoinsPos :: Hierarchy h p => [h p a] -> h p aSource

conjoinPos :: Hierarchy h p => h p a -> h p a -> h p aSource

conjoinslPos :: Hierarchy h p => h p a -> [h p a] -> h p aSource

conjoinsrPos :: Hierarchy h p => [h p a] -> h p a -> h p aSource

conjoinsPos :: Hierarchy h p => [h p a] -> h p aSource