Lazy.Tree.Zipper

Zipper implementation for Lazy.Tree.

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 to extend the default functionality of Zipper.

Types

type Zipper a

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

fromTree : Tree a -> Zipper a

Init Zipper for Tree.

import Lazy.Tree as T


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

Query

current : Zipper a -> a

Get the root item of the current Tree.

import Lazy.Tree as T


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

children : Zipper a -> List a

Get children of current Tree.

import Lazy.Tree as T


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

isRoot : Zipper a -> Bool

Check if Zipper is focused on the root Tree.

import Lazy.Tree as T


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

isEmpty : Zipper a -> Bool

Check if current Tree in Zipper is empty.

import Lazy.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 Lazy.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 matching

import Lazy.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 Lazy.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 Lazy.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 Lazy.Tree as T


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

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

Update the root item of the current Tree using given function.

import Lazy.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 Lazy.Tree as T


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

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

Open the first child that satisfies given condition. If there is no child satisfying the condition, returns Nothing.

import Lazy.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 Lazy.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 String (Zipper a)

Open multiple levels reducing list by given function.

import Lazy.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"

openAll : Zipper a -> List (Zipper a)

Get List of Zippers for all children of current Zipper

import Lazy.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 ignore failed steps.

import Lazy.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", "missing", "baz" ]
    |> current
--> "baz"

up : Zipper a -> Maybe (Zipper a)

Return back to parent of current Tree in given Zipper.

import Lazy.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 Lazy.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

Navigate back to the root Tree.

import Lazy.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 Lazy.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 information.

import Lazy.LList as LL
import Lazy.Tree as T


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


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


T.Tree 1 (LL.fromList [ 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
    |> LL.andThen (LL.map T.item << T.descendants)
    |> LL.toList
--> [ 6 ]

Breadcrumbs

breadcrumbs : Zipper a -> List a

Get List of Breadcrumbs .

import Lazy.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 Breadcrumbs as indexed List.

import Lazy.Tree as T


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

turboMaCk/lazy-tree-with-zipper/3.1.0

Lazy.Tree.Zipper

Types

Query

Operations

Transformations

Modules