Copyright | (C) 2012-16 Edward Kmett |
---|---|
License | BSD-style (see the file LICENSE) |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Stability | provisional |
Portability | Rank2Types |
Safe Haskell | Trustworthy |
Language | Haskell2010 |
This module provides combinators for breadth-first searching within arbitrary traversals.
Synopsis
- data Level i a
- levels :: Applicative f => Traversing (->) f s t a b -> IndexedLensLike Int f s t (Level () a) (Level () b)
- ilevels :: Applicative f => Traversing (Indexed i) f s t a b -> IndexedLensLike Int f s t (Level i a) (Level j b)
Documentation
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) Source # | |
Defined in Control.Lens.Internal.Level | |
FoldableWithIndex i (Level i) Source # | |
Defined in Control.Lens.Internal.Level | |
TraversableWithIndex i (Level i) Source # | |
Defined in Control.Lens.Internal.Level itraverse :: Applicative f => (i -> a -> f b) -> Level i a -> f (Level i b) # | |
Functor (Level i) Source # | |
Foldable (Level i) Source # | |
Defined in Control.Lens.Internal.Level fold :: Monoid m => Level i m -> m # foldMap :: Monoid m => (a -> m) -> Level i a -> m # foldMap' :: Monoid m => (a -> m) -> Level i a -> m # foldr :: (a -> b -> b) -> b -> Level i a -> b # foldr' :: (a -> b -> b) -> b -> Level i a -> b # foldl :: (b -> a -> b) -> b -> Level i a -> b # foldl' :: (b -> a -> b) -> b -> Level i a -> b # foldr1 :: (a -> a -> a) -> Level i a -> a # foldl1 :: (a -> a -> a) -> Level i a -> a # elem :: Eq a => a -> Level i a -> Bool # maximum :: Ord a => Level i a -> a # minimum :: Ord a => Level i a -> a # | |
Traversable (Level i) Source # | |
(Eq i, Eq a) => Eq (Level i a) Source # | |
(Ord i, Ord a) => Ord (Level i a) Source # | |
Defined in Control.Lens.Internal.Level | |
(Read i, Read a) => Read (Level i a) Source # | |
(Show i, Show a) => Show (Level i a) Source # | |
levels :: Applicative f => Traversing (->) f s t a b -> IndexedLensLike Int f s t (Level () a) (Level () b) Source #
This provides a breadth-first Traversal
or Fold
of the individual
levels
of any other Traversal
or Fold
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')]
levels
::Traversal
s t a b ->IndexedTraversal
Int
s t (Level
() a) (Level
() b)levels
::Fold
s a ->IndexedFold
Int
s (Level
() a)
Note: Internally this is implemented by using an illegal Applicative
, as it extracts information
in an order that violates the Applicative
laws.
ilevels :: Applicative f => Traversing (Indexed i) f s t a b -> IndexedLensLike Int f s t (Level i a) (Level j b) Source #
This provides a breadth-first Traversal
or Fold
of the individual
levels of any other Traversal
or Fold
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')]
ilevels
::IndexedTraversal
i s t a b ->IndexedTraversal
Int
s t (Level
i a) (Level
i b)ilevels
::IndexedFold
i s a ->IndexedFold
Int
s (Level
i a)
Note: Internally this is implemented by using an illegal Applicative
, as it extracts information
in an order that violates the Applicative
laws.