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

Language | Haskell2010 |

The Zipper is a data structure which maintains a location in a tree, and allows O(1) movement and local changes (to be more precise, in our case it is O(k) where k is the number of children of the node at question; typically this is a very small number).

- type Node f = Either (Mu f) (Path f)
- data Path f
- data Loc f = Loc {}
- root :: Mu f -> Loc f
- defocus :: Traversable f => Loc f -> Mu f
- locations :: Traversable f => Mu f -> Attr f (Loc f)
- locationsList :: Traversable f => Mu f -> [Loc f]
- locForget :: Functor f => Loc (Ann f a) -> Loc f
- extract :: Loc f -> Mu f
- replace :: Mu f -> Loc f -> Loc f
- modify :: (Mu f -> Mu f) -> Loc f -> Loc f
- moveDown :: Traversable f => Int -> Loc f -> Maybe (Loc f)
- moveDownL :: Traversable f => Loc f -> Maybe (Loc f)
- moveDownR :: Traversable f => Loc f -> Maybe (Loc f)
- moveUp :: Traversable f => Loc f -> Maybe (Loc f)
- moveRight :: Traversable f => Loc f -> Maybe (Loc f)
- moveLeft :: Traversable f => Loc f -> Maybe (Loc f)
- isTop :: Loc f -> Bool
- isBottom :: Traversable f => Loc f -> Bool
- isLeftmost :: Traversable f => Loc f -> Bool
- isRightmost :: Traversable f => Loc f -> Bool
- horizontalPos :: Foldable f => Loc f -> Int
- fullPathDown :: Foldable f => Loc f -> [Int]
- fullPathUp :: Foldable f => Loc f -> [Int]
- moveTop :: Traversable f => Loc f -> Loc f
- leftmost :: Traversable f => Loc f -> Loc f
- rightmost :: Traversable f => Loc f -> Loc f
- unsafeMoveDown :: Traversable f => Int -> Loc f -> Loc f
- unsafeMoveDownL :: Traversable f => Loc f -> Loc f
- unsafeMoveDownR :: Traversable f => Loc f -> Loc f
- unsafeMoveUp :: Traversable f => Loc f -> Loc f
- unsafeMoveLeft :: Traversable f => Loc f -> Loc f
- unsafeMoveRight :: Traversable f => Loc f -> Loc f

# Types

The context or path type. The invariant we must respect is that there is exactly
one child with the `Right`

constructor.

The zipper type itself, which encodes a locations in thre tree `Mu f`

.

# Converting to and from zippers

defocus :: Traversable f => Loc f -> Mu f Source

Restores a tree from a zipper.

locations :: Traversable f => Mu f -> Attr f (Loc f) Source

We attribute all nodes with a zipper focused at that location.

locationsList :: Traversable f => Mu f -> [Loc f] Source

The list of all locations.

# Manipulating the subtree at focus

# Safe movements

moveDown :: Traversable f => Int -> Loc f -> Maybe (Loc f) Source

Moves down to the child with the given index.
The leftmost children has index `0`

.

# Testing for borders

isBottom :: Traversable f => Loc f -> Bool Source

Checks whether we cannot move down.

isLeftmost :: Traversable f => Loc f -> Bool Source

isRightmost :: Traversable f => Loc f -> Bool Source

# Location queries

horizontalPos :: Foldable f => Loc f -> Int Source

Gives back the index of the given location among the children of its parent. Indexing starts from zero. In case of root node (no parent), we also return zero.

fullPathDown :: Foldable f => Loc f -> [Int] Source

We return the full path from the root as a sequence of child indices. This means that

loc == foldl (flip unsafeMoveDown) (moveTop loc) (fullPathDown loc)

fullPathUp :: Foldable f => Loc f -> [Int] Source

The following equations hold for `fullPathUp`

and `fullPathDown`

:

fullPathUp == reverse . fullPathDown loc == foldr unsafeMoveDown (moveTop loc) (fullPathUp loc)

# Compound movements

moveTop :: Traversable f => Loc f -> Loc f Source

Moves to the top, by repeatedly moving up.

leftmost :: Traversable f => Loc f -> Loc f Source

Moves left until it can. It should be faster than repeated left steps.

rightmost :: Traversable f => Loc f -> Loc f Source

Moves right until it can. It should be faster than repeated right steps.

# Unsafe movements

unsafeMoveDown :: Traversable f => Int -> Loc f -> Loc f Source

unsafeMoveDownL :: Traversable f => Loc f -> Loc f Source

unsafeMoveDownR :: Traversable f => Loc f -> Loc f Source

unsafeMoveUp :: Traversable f => Loc f -> Loc f Source

unsafeMoveLeft :: Traversable f => Loc f -> Loc f Source

unsafeMoveRight :: Traversable f => Loc f -> Loc f Source