Safe Haskell | Safe |
---|---|
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