hexpr- A framework for symbolic, homoiconic languages.

Safe HaskellSafe-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 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.


getPos :: h p a -> pSource

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

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

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

class Openable f whereSource

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.

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

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