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 | Safe |

Language | Haskell98 |

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

TraversableWithIndex i (Level i) Source # | |

itraverse :: Applicative f => (i -> a -> f b) -> Level i a -> f (Level i b) Source # itraversed :: (Indexable i p, Applicative f) => p a (f b) -> Level i a -> f (Level i b) Source # | |

FoldableWithIndex i (Level i) Source # | |

ifoldMap :: Monoid m => (i -> a -> m) -> Level i a -> m Source # ifolded :: (Indexable i p, Contravariant f, Applicative f) => p a (f a) -> Level i a -> f (Level i a) 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 # | |

FunctorWithIndex i (Level i) Source # | |

Functor (Level i) Source # | |

Foldable (Level i) Source # | |

fold :: Monoid m => Level i m -> 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 a, Eq i) => Eq (Level i a) Source # | |

(Ord a, Ord i) => Ord (Level i a) Source # | |

(Read a, Read i) => Read (Level i a) Source # | |

(Show a, Show i) => 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:

`>>>`

[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']`["hello","world"]^..levels (traverse.traverse)`

But we can also traverse them in turn:

`>>>`

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

We can use this to traverse to a fixed depth in the tree of (`<*>`

) used in the `Traversal`

:

`>>>`

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

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"]`["hello","world"] & taking 4 (levels (traverse.traverse).traverse) %~ toUpper`

The resulting `Traversal`

of the `levels`

which is indexed by the depth of each `Level`

.

`>>>`

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

`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.

`>>>`

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

The resulting `Traversal`

of the levels which is indexed by the depth of each `Level`

.

`>>>`

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

`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.