MultiwayTreeZipper

A library for navigating and updating immutable trees. The elements in the tree must have the same type. The trees are implemented in a Huet Zipper fashion.

Types

type Context a

= Context a (List (Tree a)) (List (Tree a))

The necessary information needed to reconstruct a MultiwayTree as it is navigated with a Zipper. This context includes the datum that was at the previous node, a list of children that came before the node, and a list of children that came after the node.

type alias Zipper a =

( Tree a, Breadcrumbs a )

A structure to keep track of the current Tree, as well as the Breadcrumbs to allow us to continue navigation through the rest of the tree.

goToChild : Int -> Zipper a -> Maybe (Zipper a)

Move down relative to the current Zipper focus. This allows navigation from a parent to it's children.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 1

goUp : Zipper a -> Maybe (Zipper a)

Move up relative to the current Zipper focus. This allows navigation from a child to it's parent.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 0
    &> goUp

goToRoot : Zipper a -> Maybe (Zipper a)

Move to the root of the current Zipper focus. This allows navigation from any part of the tree back to the root.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b"
            [ Tree "e" [] ]
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 0
    &> goToChild 1
    &> goToRoot

goLeft : Zipper a -> Maybe (Zipper a)

Move left relative to the current Zipper focus. This allows navigation from a child to it's previous sibling.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 1
    &> goLeft

goRight : Zipper a -> Maybe (Zipper a)

Move right relative to the current Zipper focus. This allows navigation from a child to it's next sibling.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 1
    &> goRight

goToNext : Zipper a -> Maybe (Zipper a)

Moves to the next node in the hierarchy, depth-first. If already at the end, stays there.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToNext
    &> goToNext

goToPrevious : Zipper a -> Maybe (Zipper a)

Moves to the previous node in the hierarchy, depth-first.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 2
    &> goToPrevious
    &> goToPrevious

goToRightMostChild : Zipper a -> Maybe (Zipper a)

Move down and as far right as possible relative to the current Zipper focus. This allows navigation from a parent to it's last child.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b" []
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToRightMostChild

Update API

updateDatum : (a -> a) -> Zipper a -> Maybe (Zipper a)

Update the datum at the current Zipper focus. This allows changes to be made to a part of a node's datum information, given the previous state of the node.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b"
            [ Tree "e" [] ]
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 0
    &> updateDatum (\old -> old ++ "X") -- Appends an X to "b"
    &> goToRoot

replaceDatum : a -> Zipper a -> Maybe (Zipper a)

Replace the datum at the current Zipper focus. This allows complete replacement of a node's datum information, ignoring the previous state of the node.

(&>) = Maybe.andThen


simpleTree =
    Tree "a"
        [ Tree "b"
            [ Tree "e" [] ]
        , Tree "c" []
        , Tree "d" []
        ]


Just (simpleTree, [])
    &> goToChild 0
    &> replaceDatum "X" -- Replaces "b" with "X"
    &> goToRoot

Access API

datum : Zipper a -> a

Access the datum at the current Zipper focus.

maybeDatum : Zipper a -> Maybe a

Access the datum at the current Zipper focus as a Maybe.

References

The Zipper, Gerard Huet Learn You A Haskell, Zippers, Miran Lipovaca

Future work

Might be able to integrate existing Rose Tree to work with the Zipper. Wanted the first version to be self contained.

tomjkidd/elm-multiway-tree-zipper/1.5.0