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)

Defined in Data.Generics.Fixplate.Zipper

Methods

(==) :: Path f -> Path f -> Bool

(/=) :: Path f -> Path f -> Bool

ReadF f => Read (Path f)

Defined in Data.Generics.Fixplate.Zipper

Methods

readsPrec :: Int -> ReadS (Path f)

readList :: ReadS [Path f]

readPrec :: ReadPrec (Path f)

readListPrec :: ReadPrec [Path f]

ShowF f => Show (Path f)

Defined in Data.Generics.Fixplate.Zipper

Methods

showsPrec :: Int -> Path f -> ShowS

show :: Path f -> String

showList :: [Path f] -> ShowS

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)

Defined in Data.Generics.Fixplate.Zipper

Methods

(==) :: Loc f -> Loc f -> Bool

(/=) :: Loc f -> Loc f -> Bool

ReadF f => Read (Loc f)

Defined in Data.Generics.Fixplate.Zipper

Methods

readsPrec :: Int -> ReadS (Loc f)

readList :: ReadS [Loc f]

readPrec :: ReadPrec (Loc f)

readListPrec :: ReadPrec [Loc f]

ShowF f => Show (Loc f)

Defined in Data.Generics.Fixplate.Zipper

Methods

showsPrec :: Int -> Loc f -> ShowS

show :: Loc f -> String

showList :: [Loc f] -> ShowS

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

Location queries

horizontalPos :: Foldable f => Loc f -> Int

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]

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]

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

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

unsafeMoveRight :: Traversable f => Loc f -> Loc f