Tree.Zipper

Zipper implementation.

A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages.

Zipper is a secret sauce that gives Tree real power. It provides an easy way to query and modify the Tree in a clever and very flexible way.

Types within this module are exposed type aliases to make it easy extend default functionality of Zipper.

Types

type Zipper a

= Zipper (Tree a) (List (Breadcrumb a))

fromTree : Tree a -> Zipper a

Init Zipper for Tree.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> current
--> "foo"

Query

current : Zipper a -> a

Get item of current Tree.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> current
--> "foo"

children : Zipper a -> List a

Get children of current Tree.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> children
--> [ "bar" ]

isRoot : Zipper a -> Bool

Check if Zipper is focused on root Tree.

import Tree as T


T.singleton "foo"
   |> fromTree
   |> isRoot
--> True

isEmpty : Zipper a -> Bool

Check if current Tree in Zipper is empty.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> isEmpty
--> True


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> isEmpty
--> False

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

Attempt to perform action over zipper and return original Zipper in cases where this action returns Nothing.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> attempt delete
    |> current
--> "foo"


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> attempt (open ((==) "foo"))
    |> attempt delete
    |> current
--> "foo"

getTree : Zipper a -> Tree a

Extract current Tree from a Zipper.

useful in case where you don't want to use pattern mathcing

import Tree as T


T.singleton "foo"
    |> fromTree
    |> getTree
    |> T.item
--> "foo"

Operations

insert : Tree a -> Zipper a -> Zipper a

Insert sub Tree into current Tree in Zipper.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> insert (T.singleton "baz")
    |> children
--> [ "bar", "baz" ]

delete : Zipper a -> Maybe (Zipper a)

Delete current Tree from Zipper.

Returns Nothing if root node is removed.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> delete
--> Nothing


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> open (always True)
    |> Maybe.andThen delete
    |> Maybe.map current
--> Just "foo"

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

Update current Tree using given function.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> update (T.map (\a -> a ++ " fighter"))
    |> current
--> "foo fighter"

updateItem : (a -> a) -> Zipper a -> Zipper a

Update item of current Tree using given function.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> updateItem (\i -> i ++ " fighter")
    |> current
--> "foo fighter"

setTree : Tree a -> Zipper a -> Zipper a

Replace current Tree with new one.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> setTree (T.singleton "bar")
    |> current
--> "bar"

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

Open first children that satisfy given condition.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> open ((==) "bar")
    |> Maybe.map current
--> Just "bar"


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz") )
    |> attempt (open ((==) "bar"))
    |> attempt (open ((==) "baz"))
    |> current
--> "baz"


T.singleton "foo"
    |> fromTree
    |> open (always True)
--> Nothing

getPath : (a -> b) -> Zipper a -> List b

Use given function to convert current breadcrumb path to a list

Resulting list of breadcrumbs contains currently focused item as well.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> attemptOpenPath (==) [ "bar" ]
    |> getPath identity
--> [ "foo", "bar" ]


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz") )
    |> attemptOpenPath (==) [ "bar", "baz" ]
    |> getPath identity
--> [ "foo", "bar", "baz" ]

openPath : (b -> a -> Bool) -> List b -> Zipper a -> Result b (Zipper a)

Open multiple levels reducing list by given function.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz") )
    |> openPath (==) [ "bar", "baz" ]
    |> Result.map current
--> Ok "baz"


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> openPath (==) [ "not-here", "baz" ]
    |> Result.map current
--> Err "Can't resolve open for \"not-here\""

openAll : Zipper a -> List (Zipper a)

Get List of Zippers for all children of current Zipper

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> insert (T.singleton "baz")
    |> openAll
    |> List.map current
--> [ "bar", "baz" ]

attemptOpenPath : (b -> a -> Bool) -> List b -> Zipper a -> Zipper a

Similar to openPath but ingnore failed steps.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> attemptOpenPath (==) [ "not-here", "bar" ]
    |> current
--> "bar"


T.singleton "foo"
    |> fromTree
    |> attemptOpenPath (==) [ "baz" ]
    |> current
--> "foo"


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz"))
    |> attemptOpenPath (==) [ "not-here", "bar", "missng", "baz" ]
    |> current
--> "baz"

up : Zipper a -> Maybe (Zipper a)

Return back to parent of current Tree in given Zipper.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar")
    |> open ((==) "bar")
    |> Maybe.andThen up
    |> Maybe.map current
--> Just "foo"


T.singleton "baz"
    |> fromTree
    |> up
--> Nothing

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

Perform up n times.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz") )
    |> open ((==) "bar")
    |> Maybe.andThen (open ((==) "baz"))
    |> Maybe.andThen (upwards 2)
    |> Maybe.map current
--> Just "foo"

Returns given Zipper return if 0 is passed:

T.singleton "foo"
   |> fromTree
   |> upwards 0
   |> Maybe.map current
--> Just "foo"

Return Nothing if there are not enough ancestors in Zipper:

T.singleton 4
    |> fromTree
    |> upwards 1
--> Nothing

Return Nothing if negative integer is passed:

T.singleton 4
    |> fromTree
    |> upwards -1
--> Nothing

root : Zipper a -> Zipper a

Back to root Tree.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz") )
    |> open ((==) "bar")
    |> Maybe.andThen (open ((==) "baz"))
    |> Maybe.map root
    |> Maybe.map current
--> Just "foo"


T.singleton "foo"
    |> fromTree
    |> root
    |> current
--> "foo"

Transformations

map : (a -> b) -> Zipper a -> Zipper b

Map function over Zipper.

import Tree as T


T.singleton 1
    |> fromTree
    |> map ((+) 1)
    |> current
--> 2

filter : (a -> Bool) -> Zipper a -> Zipper a

Performs filter on current Tree in Zipper. See Tree.filter for more informations.

import Tree as T


T.Tree 1 [ T.singleton 2, T.singleton 3, T.singleton 4 ]
    |> fromTree
    |> filter ((>) 4)
    |> children
--> [ 2, 3 ]


T.Tree 1 [ T.singleton 2, T.singleton 3, T.singleton 4 ]
    |> fromTree
    |> attempt (open ((==) 1))
    |> filter ((<) 2)
    |> root
    |> children
--> [ 3, 4 ]


T.Tree 1 [ T.insert (T.singleton 5) <| T.singleton 2, T.insert (T.singleton 6) <| T.singleton 3, T.singleton 4 ]
    |> fromTree
    |> attempt (open ((==) 1))
    |> filter ((<) 2)
    |> getTree
    |> T.descendants
    |> List.andThen (List.map T.item << T.descendants)
--> [ 6 ]

Breadcrumbs

breadcrumbs : Zipper a -> List a

Get List of Breacrubs .

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz"))
    |> attemptOpenPath (==) [ "bar", "baz" ]
    |> breadcrumbs
--> [ "bar", "foo" ]

indexedBreadcrumbs : Zipper a -> List ( Int, a )

Get Breacrubs as indexed List.

import Tree as T


T.singleton "foo"
    |> fromTree
    |> insert (T.singleton "bar" |> T.insert (T.singleton "baz"))
    |> attemptOpenPath (==) [ "bar", "baz" ]
    |> indexedBreadcrumbs
--> [ ( 1, "bar" ), ( 2, "foo" )]

miyamoen/tree-with-zipper/1.0.0

Tree.Zipper

Types

Query

Operations

Transformations

Modules