fixplate-0.1.1: Uniplate-style generic traversals for fixed-point types, with some extras.

Data.Generics.Fixplate.Zipper

Contents

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.

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.

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