Safe Haskell | Safe |
---|---|

Language | Haskell98 |

A slightly experimental add-on for Alloy involving the idea of routes to a particular part of a tree.

- data Route inner outer
- routeModify :: Route inner outer -> (inner -> inner) -> outer -> outer
- routeModifyM :: Monad m => Route inner outer -> (inner -> m inner) -> outer -> m outer
- routeGet :: Route inner outer -> outer -> inner
- routeSet :: Route inner outer -> inner -> outer -> outer
- (@->) :: Route mid outer -> Route inner mid -> Route inner outer
- identityRoute :: Route a a
- routeId :: Route inner outer -> [Int]
- routeList :: Int -> Route a [a]
- makeRoute :: [Int] -> (forall m. Monad m => (inner -> m inner) -> outer -> m outer) -> Route inner outer
- routeDataMap :: Ord k => Int -> Route (k, v) (Map k v)
- routeDataSet :: Ord k => Int -> Route k (Set k)
- class AlloyARoute t o o' where
- transformMRoute :: Monad m => o m outer -> o' m outer -> (t, Route t outer) -> m t
- transformARoute :: Applicative f => o f outer -> o' f outer -> (t, Route t outer) -> f t

- data BaseOpARoute m outer = BaseOpARoute
- baseOpARoute :: BaseOpARoute m outer
- data (t :-@ opT) m outer = ((t, Route t outer) -> m t) :-@ (opT m outer)
- type OneOpARoute t = t :-@ BaseOpARoute
- type TwoOpARoute s t = s :-@ (t :-@ BaseOpARoute)

# Documentation

A Route is a way of navigating to a particular node in a tree structure.

Let's say that you have some binary tree structure:

data BinTree a = Leaf a | Branch (BinTree a) (BinTree a)

Suppose you then have a big binary tree of integers, potentially with duplicate values, and you want to be able to modify a particular integer. You can't modify in-place, because this is a functional language. So you instead want to be able to apply a modify function to the whole tree that really just modifies the particular integer, deep within the tree.

To do this you can use a route:

myRoute :: Route Int (BinTree Int)

You apply it as follows (for example, to increment the integer):

routeModify myRoute (+1) myTree

This will only work if the route is valid on the given tree.

The usual way that you get routes is via the traversal functions in the module.

Another useful aspect is composition. If your tree was in a tree of trees:

routeToInnerTree :: Route (BinTree Int) (BinTree (BinTree Int))

You could compose this with the earlier route:

routeToInnerTree @-> myRoute :: Route Int (BinTree (BinTree Int))

These routes are a little like zippers, but rather than building a new data type to contain the zipped version and the re-use aspect, this is just a simple add-on to apply a modification function in a particular part of the tree. Multiple routes can be used to modify the same tree, which is also useful.

Routes support Eq, Show and Ord. All these instances represent a route as a list of integers: a route-map. [0,2,1] means first child (zero-based), then third child, then second child of the given data-type. Routes are ordered using the standard list ordering (lexicographic) over this representation.

routeModify :: Route inner outer -> (inner -> inner) -> outer -> outer Source

Applies a pure modification function using the given route.

routeModifyM :: Monad m => Route inner outer -> (inner -> m inner) -> outer -> m outer Source

Applies a monadic modification function using the given route.

routeGet :: Route inner outer -> outer -> inner Source

Given a route, gets the value in the large data structure that is pointed to by that route.

routeSet :: Route inner outer -> inner -> outer -> outer Source

Given a route, sets the value in the large data structure that is pointed to by that route.

(@->) :: Route mid outer -> Route inner mid -> Route inner outer Source

Composes two routes together. The outer-to-mid route goes on the left hand side, and the mid-to-inner goes on the right hand side to form an outer-to-inner route.

identityRoute :: Route a a Source

The identity route. This has various obvious properties:

routeGet identityRoute == id routeSet identityRoute == const routeModify identityRoute == id identityRoute @-> route == route route @-> identityRoute == route

routeId :: Route inner outer -> [Int] Source

Gets the integer-list version of a route. See the documentation of `Route`

.

routeList :: Int -> Route a [a] Source

Given an index (zero is the first item), forms a route to that index item in the list. So for example:

routeModify (routeList 3) (*10) [0,1,2,3,4,5] == [0,1,2,30,4,5]

makeRoute :: [Int] -> (forall m. Monad m => (inner -> m inner) -> outer -> m outer) -> Route inner outer Source

Given the integer list of identifiers and the modification function, forms
a Route. It is up to you to make sure that the integer list is valid as described
in the documentation of `Route`

, otherwise routes constructed this way and via
the Alloy functions may exhibit strange behaviours when compared.

routeDataMap :: Ord k => Int -> Route (k, v) (Map k v) Source

Constructs a Route to the key-value pair at the given index (zero-based) in the ordered map. Routes involving maps are difficult because Map hides its internal representation. This route secretly boxes the Map into a list of pairs and back again when used. The identifiers for map entries (as used in the integer list) are simply the index into the map as passed to this function.

routeDataSet :: Ord k => Int -> Route k (Set k) Source

Constructs a Route to the value at the given index (zero-based) in the ordered
set. See the documentation for `routeDataMap`

, which is nearly identical to
this function.

class AlloyARoute t o o' where Source

An extension to `AlloyA`

that adds in `Route`

s. The opsets are now parameterised
over both the monad/functor, and the outer-type of the route.

transformMRoute :: Monad m => o m outer -> o' m outer -> (t, Route t outer) -> m t Source

transformARoute :: Applicative f => o f outer -> o' f outer -> (t, Route t outer) -> f t Source

baseOpARoute :: BaseOpARoute m outer Source

Like `baseOpA`

but for `AlloyARoute`

.

data (t :-@ opT) m outer infixr 7 Source

The type that extends an applicative/monadic opset (opT) in the given
functor/monad (m) to be applied to the given type (t) with routes to the
outer type (outer). This is for use with the `AlloyARoute`

class.

type OneOpARoute t = t :-@ BaseOpARoute Source

A handy synonym for a monadic/applicative opset with only one item, to use with `AlloyARoute`

.

type TwoOpARoute s t = s :-@ (t :-@ BaseOpARoute) Source

A handy synonym for a monadic/applicative opset with only two items, to use with `AlloyARoute`

.