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

Control.Lens.Level

Description

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

data Level i a Source #

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

Instances details

FunctorWithIndex i ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods imap :: (i -> a -> b) -> Level i a -> Level i b Source #
FoldableWithIndex i ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods ifoldMap :: Monoid m => (i -> a -> m) -> Level i a -> m Source # ifoldMap' :: Monoid m => (i -> a -> m) -> Level i a -> m Source # ifoldr :: (i -> a -> b -> b) -> b -> Level i a -> b Source # ifoldl :: (i -> b -> a -> b) -> b -> Level i a -> b Source # ifoldr' :: (i -> a -> b -> b) -> b -> Level i a -> b Source # ifoldl' :: (i -> b -> a -> b) -> b -> Level i a -> b Source #
TraversableWithIndex i ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods itraverse :: Applicative f => (i -> a -> f b) -> Level i a -> f ( Level i b) Source #
Functor ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods fmap :: (a -> b) -> Level i a -> Level i b Source # (<$) :: a -> Level i b -> Level i a Source #
Foldable ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods fold :: Monoid m => Level i m -> m Source # foldMap :: Monoid m => (a -> m) -> Level i a -> m Source # foldMap' :: Monoid m => (a -> m) -> Level i a -> m Source # foldr :: (a -> b -> b) -> b -> Level i a -> b Source # foldr' :: (a -> b -> b) -> b -> Level i a -> b Source # foldl :: (b -> a -> b) -> b -> Level i a -> b Source # foldl' :: (b -> a -> b) -> b -> Level i a -> b Source # foldr1 :: (a -> a -> a) -> Level i a -> a Source # foldl1 :: (a -> a -> a) -> Level i a -> a Source # toList :: Level i a -> [a] Source # null :: Level i a -> Bool Source # length :: Level i a -> Int Source # elem :: Eq a => a -> Level i a -> Bool Source # maximum :: Ord a => Level i a -> a Source # minimum :: Ord a => Level i a -> a Source # sum :: Num a => Level i a -> a Source # product :: Num a => Level i a -> a Source #
Traversable ( Level i) Source #
Instance details Defined in Control.Lens.Internal.Level Methods traverse :: Applicative f => (a -> f b) -> Level i a -> f ( Level i b) Source # sequenceA :: Applicative f => Level i (f a) -> f ( Level i a) Source # mapM :: Monad m => (a -> m b) -> Level i a -> m ( Level i b) Source # sequence :: Monad m => Level i (m a) -> m ( Level i a) Source #
( Eq i, Eq a) => Eq ( Level i a) Source #
Instance details Defined in Control.Lens.Internal.Level Methods (==) :: Level i a -> Level i a -> Bool Source # (/=) :: Level i a -> Level i a -> Bool Source #
( Ord i, Ord a) => Ord ( Level i a) Source #
Instance details Defined in Control.Lens.Internal.Level Methods compare :: Level i a -> Level i a -> Ordering Source # (<) :: Level i a -> Level i a -> Bool Source # (<=) :: Level i a -> Level i a -> Bool Source # (>) :: Level i a -> Level i a -> Bool Source # (>=) :: Level i a -> Level i a -> Bool Source # max :: Level i a -> Level i a -> Level i a Source # min :: Level i a -> Level i a -> Level i a Source #
( Read i, Read a) => Read ( Level i a) Source #
Instance details Defined in Control.Lens.Internal.Level Methods readsPrec :: Int -> ReadS ( Level i a) Source # readList :: ReadS [ Level i a] Source # readPrec :: ReadPrec ( Level i a) Source # readListPrec :: ReadPrec [ Level i a] Source #
( Show i, Show a) => Show ( Level i a) Source #
Instance details Defined in Control.Lens.Internal.Level Methods showsPrec :: Int -> Level i a -> ShowS Source # show :: Level i a -> String Source # showList :: [ Level i a] -> ShowS 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.