Data.Generics.Fixplate.Zipper

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

Types

type Node f = Either (Mu f) (Path f)

A context node.

data Path f

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

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 f

Creates a zipper from a tree, with the focus at the root.

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

Restores a tree from a zipper.

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

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

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

The list of all locations.

locForget :: Functor f => Loc (Ann f a) -> Loc f

The zipper version of forget.

Manipulating the subtree at focus

extract :: Loc f -> Mu f

Extracts the subtree at focus. Synonym of focus.

replace :: Mu f -> Loc f -> Loc f

Replaces the subtree at focus.

modify :: (Mu f -> Mu f) -> Loc f -> Loc f

Modifies the subtree at focus.

Safe movements

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

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

moveDownL :: Traversable f => Loc f -> Maybe (Loc f)

Moves down to the leftmost child.

moveDownR :: Traversable f => Loc f -> Maybe (Loc f)

Moves down to the rightmost child.

moveUp :: Traversable f => Loc f -> Maybe (Loc f)

Moves up.

moveRight :: Traversable f => Loc f -> Maybe (Loc f)

moveLeft :: Traversable f => Loc f -> Maybe (Loc f)

Testing for borders

isTop :: Loc f -> Bool

Checks whether we are at the top (root).

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

Checks whether we cannot move down.

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

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

Compound movements

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

Moves to the top, by repeatedly moving up.

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

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

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

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

Unsafe movements

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, unsafeMoveRight :: Traversable f => Loc f -> Loc f