Safe Haskell	Safe-Infered

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

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
Fields unPath :: f (Node f)

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
Fields focus :: Mu f path :: Path f

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 -> Bool Source

Checks whether we are at the top (root).

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

unsafeMoveLeft, unsafeMoveRight :: Traversable f => Loc f -> Loc fSource