fixplate-0.1.5: Uniplate-style generic traversals for optionally annotated fixed-point types.Source codeContentsIndex
Data.Generics.Fixplate.Zipper
Contents
Types
Converting to and from zippers
Manipulating the subtree at focus
Safe movements
Testing for borders
Location queries
Compound movements
Unsafe movements
Description
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).
Synopsis
type Node f = Either (Mu f) (Path f)
data Path f
= Top
| Path {
unPath :: f (Node f)
}
data Loc f = Loc {
focus :: Mu f
path :: Path f
}
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
unsafeMoveRight :: Traversable f => Loc f -> Loc f
unsafeMoveLeft :: Traversable f => Loc f -> Loc f
Types
type Node f = Either (Mu f) (Path f)Source
A context node.
data Path f Source
The context or path type. The invariant we must respect is that there is exactly one child with the Right constructor.
Constructors
Top
Path
unPath :: f (Node f)
show/hide Instances
EqF f => Eq (Path f)
ReadF f => Read (Path f)
ShowF f => Show (Path f)
data Loc f Source
The zipper type itself, which encodes a locations in thre tree Mu f.
Constructors
Loc
focus :: Mu f
path :: Path f
show/hide Instances
EqF f => Eq (Loc f)
ReadF f => Read (Loc f)
ShowF f => Show (Loc f)
Converting to and from zippers
root :: Mu f -> Loc fSource
Creates a zipper from a tree, with the focus at the root.
defocus :: Traversable f => Loc f -> Mu fSource
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.
locForget :: Functor f => Loc (Ann f a) -> Loc fSource
The zipper version of forget.
Manipulating the subtree at focus
extract :: Loc f -> Mu fSource
Extracts the subtree at focus. Synonym of focus.
replace :: Mu f -> Loc f -> Loc fSource
Replaces the subtree at focus.
modify :: (Mu f -> Mu f) -> Loc f -> Loc fSource
Modifies 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.
moveDownL :: Traversable f => Loc f -> Maybe (Loc f)Source
Moves down to the leftmost child.
moveDownR :: Traversable f => Loc f -> Maybe (Loc f)Source
Moves down to the rightmost child.
moveUp :: Traversable f => Loc f -> Maybe (Loc f)Source
Moves up.
moveRight :: Traversable f => Loc f -> Maybe (Loc f)Source
moveLeft :: Traversable f => Loc f -> Maybe (Loc f)Source
Testing for borders
isTop :: Loc f -> BoolSource
Checks whether we are at the top (root).
isBottom :: Traversable f => Loc f -> BoolSource
Checks whether we cannot move down.
isLeftmost :: Traversable f => Loc f -> BoolSource
isRightmost :: Traversable f => Loc f -> BoolSource
Location queries
horizontalPos :: Foldable f => Loc f -> IntSource
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 fSource
Moves to the top, by repeatedly moving up.
leftmost :: Traversable f => Loc f -> Loc fSource
Moves left until it can. It should be faster than repeated left steps.
rightmost :: Traversable f => Loc f -> Loc fSource
Moves right until it can. It should be faster than repeated right steps.
Unsafe movements
unsafeMoveDown :: Traversable f => Int -> Loc f -> Loc fSource
unsafeMoveDownL :: Traversable f => Loc f -> Loc fSource
unsafeMoveDownR :: Traversable f => Loc f -> Loc fSource
unsafeMoveUp :: Traversable f => Loc f -> Loc fSource
unsafeMoveRight :: Traversable f => Loc f -> Loc fSource
unsafeMoveLeft :: Traversable f => Loc f -> Loc fSource
Produced by Haddock version 2.6.1