Control.Lens.Level

This module provides combinators for breadth-first searching within arbitrary traversals.

Documentation

data Level i a

This data type represents a path-compressed copy of one level of a source data structure. We can safely use path-compression because we know the depth of the tree.

Path compression is performed by viewing a Level as a PATRICIA trie of the paths into the structure to leaves at a given depth, similar in many ways to a IntMap, but unlike a regular PATRICIA trie we do not need to store the mask bits merely the depth of the fork.

One invariant of this structure is that underneath a Two node you will not find any Zero nodes, so Zero can only occur at the root.

Instances

(FunctorWithIndex i (Level i), FoldableWithIndex i (Level i), Traversable (Level i)) => TraversableWithIndex i (Level i)

Foldable (Level i) => FoldableWithIndex i (Level i)

Functor (Level i) => FunctorWithIndex i (Level i)

Functor (Level i)

Foldable (Level i)

(Functor (Level i), Foldable (Level i)) => Traversable (Level i)

(Eq i, Eq a) => Eq (Level i a)

(Eq (Level i a), Ord i, Ord a) => Ord (Level i a)

(Read i, Read a) => Read (Level i a)

(Show i, Show a) => Show (Level i a)

levels :: ATraversal s t a b -> IndexedTraversal Int s t (Level () a) (Level () b)

This provides a breadth-first Traversal of the individual levels of any other Traversal via iterative deepening depth-first search. The levels are returned to you in a compressed format.

This can permit us to extract the levels directly:

>>> ["hello","world"]^..levels (traverse.traverse)
[Zero,Zero,One () 'h',Two 0 (One () 'e') (One () 'w'),Two 0 (One () 'l') (One () 'o'),Two 0 (One () 'l') (One () 'r'),Two 0 (One () 'o') (One () 'l'),One () 'd']

But we can also traverse them in turn:

>>> ["hello","world"]^..levels (traverse.traverse).traverse
"hewlolrold"

We can use this to traverse to a fixed depth in the tree of (<*>) used in the Traversal:

>>> ["hello","world"] & taking 4 (levels (traverse.traverse)).traverse %~ toUpper
["HEllo","World"]

Or we can use it to traverse the first n elements in found in that Traversal regardless of the depth at which they were found.

>>> ["hello","world"] & taking 4 (levels (traverse.traverse).traverse) %~ toUpper
["HELlo","World"]

The resulting Traversal of the levels which is indexed by the depth of each Level.

>>> ["dog","cat"]^@..levels (traverse.traverse) <. traverse
[(2,'d'),(3,'o'),(3,'c'),(4,'g'),(4,'a'),(5,'t')]

Note: Internally this is implemented by using an illegal Applicative, as it extracts information in an order that violates the Applicative laws.

ilevels :: AnIndexedTraversal i s t a b -> IndexedTraversal Int s t (Level i a) (Level j b)

This provides a breadth-first Traversal of the individual levels of any other Traversal via iterative deepening depth-first search. The levels are returned to you in a compressed format.

This is similar to levels, but retains the index of the original IndexedTraversal, so you can access it when traversing the levels later on.

>>> ["dog","cat"]^@..ilevels (traversed<.>traversed).itraversed
[((0,0),'d'),((0,1),'o'),((1,0),'c'),((0,2),'g'),((1,1),'a'),((1,2),'t')]

The resulting Traversal of the levels which is indexed by the depth of each Level.

>>> ["dog","cat"]^@..ilevels (traversed<.>traversed)<.>itraversed
[((2,(0,0)),'d'),((3,(0,1)),'o'),((3,(1,0)),'c'),((4,(0,2)),'g'),((4,(1,1)),'a'),((5,(1,2)),'t')]

Note: Internally this is implemented by using an illegal Applicative, as it extracts information in an order that violates the Applicative laws.