Tree.Zipper

Imagine walking through a Tree structure. You can step from a node to its parent, its children or one of its sibling. At every step of the way, you're "at" a tree. A Tree.Zipper represents such a step, and offers an API to navigate and modify the tree structure while walking through it.

Structure

type Zipper a

Represents a location within a tree, always pointing at the root or one of its descendant trees.

fromTree : Tree a -> Zipper a

To start your journey, you need to start at a tree. fromTree creates a zipper with the given tree as its root.

import Tree exposing (Tree)




myTree : Tree Int
myTree =
    Tree.tree 1
        [ Tree.singleton 2
        , Tree.singleton 3
        ]




fromTree myTree
    |> label
--> 1

toTree : Zipper a -> Tree a

toTree rebuilds the tree to its root, and returns that.

import Tree exposing (Tree)




myTree : Tree Int
myTree =
    Tree.tree 1
        [ Tree.singleton 2
        , Tree.singleton 3
        ]




fromTree myTree
    |> lastDescendant
    |> mapLabel (\x -> x * 2)
    |> toTree
--> Tree.tree 1
-->     [ Tree.singleton 2
-->     , Tree.singleton 6
-->     ]

tree : Zipper a -> Tree a

Sometimes you don't want to extract the tree from the root, but just look at the tree that's current in "in focus" in isolation.

import Tree exposing (Tree)




myTree : Tree Int
myTree =
    Tree.tree 1
        [ Tree.singleton 2
        , Tree.singleton 3
        ]




fromTree myTree
    |> lastDescendant
    |> mapLabel (\x -> x * 2)
    |> tree
--> Tree.singleton 6

label : Zipper a -> a

The label of the currently focused tree.

children : Zipper a -> List (Tree a)

The children of the currently focused tree.

firstChild : Zipper a -> Maybe (Zipper a)

Move to the first child of the currently focused tree, if it has children.

If the current tree is a singeton, this returns Nothing.

import Tree exposing (Tree)




fromTree (Tree.singleton "root")
    |> firstChild
--> Nothing




Tree.tree "root"
    [ Tree.singleton "child" ]
    |> fromTree
    |> firstChild
    |> Maybe.map label
--> Just "child"

lastChild : Zipper a -> Maybe (Zipper a)

If the current tree has children, move to the last of those.

import Tree exposing (Tree)




myTree : Tree String
myTree =
    Tree.tree "root"
        [ Tree.singleton "first"
        , Tree.tree "last child"
            [ Tree.singleton "child of last child"
            ]
        ]




fromTree myTree
    |> lastChild
    |> Maybe.map label
--> Just "last child"




fromTree myTree
    |> lastChild
    |> Maybe.andThen lastChild
    |> Maybe.map label
--> Just "child of last child"

parent : Zipper a -> Maybe (Zipper a)

Move to the parent. If the focus is on the root, there is no parent and this returns Nothing.

import Tree exposing (Tree)




fromTree (Tree.singleton "root")
    |> parent
--> Nothing




Tree.tree "root"
    [ Tree.singleton "child" ]
    |> fromTree
    |> firstChild
    |> Maybe.andThen parent
    |> Maybe.map label
--> Just "root"

forward : Zipper a -> Maybe (Zipper a)

Try to move "forward". This means either to the first child, the next sibling, the next descendant of an ancestor or - if all else fails - Nothing.

import Tree exposing (Tree)


myTree : Tree String
myTree =
    Tree.tree "root"
        [ Tree.singleton "first child"
        , Tree.tree "second child"
            [ Tree.singleton "third child" ]
        , Tree.singleton "last child"
        ]

First direction is to go down to the first child.

fromTree myTree
    |> forward
    |> Maybe.map label
--> Just "first child"

Since the first child doesn't have children of its own, the next step is to go to the next sibling.

fromTree myTree
    |> forward
    |> Maybe.andThen forward
    |> Maybe.map label
--> Just "second child"

The next sibling does have a child, so we go there, next.

fromTree myTree
    |> forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
    |> Maybe.map label
--> Just "third child"

The third child doesn't have children or siblings. However, its parent does, so we go up a level and to the next sibling. If the direct parent doesn't have a next sibling either, forward will look up the chain of ancestors one that has a sibling.

fromTree myTree
    |> forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
    |> Maybe.map label
--> Just "last child"

Finally, after the last child, there is no next node - it doesn't have children, no next siblings, and no ancestors that have any siblings left. So, we've reached the end of the tree.

fromTree myTree
    |> forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
    |> Maybe.andThen forward
--> Nothing

backward : Zipper a -> Maybe (Zipper a)

backward is the inverse of forward. As such, it will first try to go the last descendant of a previous sibling, or the previous sibling if it has no descendants. If there are no previous siblings, it will move up to its parent.

If all else fails (i.e. you are at the root) this returns Nothing.

import Tree exposing (Tree)


myTree : Tree String
myTree =
    Tree.tree "root"
        [ Tree.singleton "first child"
        , Tree.tree "second child"
            [ Tree.singleton "third child" ]
        , Tree.singleton "last child"
        ]




fromTree myTree
    |> lastDescendant -- Focus on "last child"
    |> backward -- jump to the last child of the previous sibling
    |> Maybe.map label
--> Just "third child"




fromTree myTree
    |> backward
--> Nothing

root : Zipper a -> Zipper a

From anywhere, this zooms back up to the root of the tree.

This is essentially equivalent to executing parent over and over as long as it succeeds.

lastDescendant : Zipper a -> Zipper a

The inverse of root. Think of it as repeating lastChild as long as it returns something.

Note that this will only try to descent within the current focus.

import Tree exposing (Tree)




myTree : Tree Int
myTree =
    Tree.tree 0
        [ Tree.tree 1
            [ Tree.singleton 2
            , Tree.singleton 3
            ]
        , Tree.tree 4
            [ Tree.singleton 5 ]
        ]




fromTree myTree
    |> lastDescendant
    |> label
--> 5




fromTree myTree
    |> firstChild
    |> Maybe.map lastDescendant
    |> Maybe.map label
--> Just 3

nextSibling : Zipper a -> Maybe (Zipper a)

Does what it says on the tin. Move to the next sibling if the node has some more siblings left.

previousSibling : Zipper a -> Maybe (Zipper a)

Not too surprisingly, moves to the previous sibling if there are any.

In particular, this returns Nothing for nodes that are the first child or the root.

Modification

mapTree : (Tree a -> Tree a) -> Zipper a -> Zipper a

Execute a function on the currently focused tree, replacing it in the zipper.

replaceTree : Tree a -> Zipper a -> Zipper a

Replace the currently focused tree in the zipper with a different one.

mapLabel : (a -> a) -> Zipper a -> Zipper a

Map a function on the label of the currently focused tree.

replaceLabel : a -> Zipper a -> Zipper a

Replace the label of the currently focused tree.

append : Tree a -> Zipper a -> Zipper a

Append a tree as a sibling after the currently focused tree. If the current tree is the root, this is a no-op.

prepend : Tree a -> Zipper a -> Zipper a

Prepend a tree as a sibling before the currently focused tree. If the current tree is the root, this is a no-op.

Utility

findNext : (a -> Bool) -> Zipper a -> Maybe (Zipper a)

Looks for a matching tree after the current focus, using forward to navigate. Excludes the current focus.

findPrevious : (a -> Bool) -> Zipper a -> Maybe (Zipper a)

Looks for a matching tree before the current focus, using backward to navigate. Excludes the current focus.

findFromRoot : (a -> Bool) -> Zipper a -> Maybe (Zipper a)

Find a tree whose label matches a given predicate, starting from (and including) the root of the tree this zipper operates over.

zwilias/elm-rosetree/1.1.0

Tree.Zipper

Structure

Navigation

Modification

Utility

Modules