Control.Lens.Traversal

A Traversal a b c d is a generalization of traverse from Traversable. It allows you to traverse over a structure and change out its contents with monadic or applicative side-effects. Starting from

traverse :: (Traversable t, Applicative f) => (c -> f d) -> t c -> f (t d),

we monomorphize the contents and result to obtain

 type Traversal a b c d = forall f. Applicative f => (c -> f d) -> a -> f b

While a Traversal isn't quite a Fold, it _can_ be used for Getting like a Fold, because given a Monoid m, we have an Applicative for (Const m). Everything you know how to do with a Traversable container, you can with with a Traversal, and here we provide combinators that generalize the usual Traversable operations.

Lenses

type Traversal a b c d = forall f. Applicative f => (c -> f d) -> a -> f b

A Traversal can be used directly as a Setter or a Fold (but not as a Lens) and provides the ability to both read and update multiple fields, subject to some relatively weak Traversal laws.

These have also been known as multilenses, but they have the signature and spirit of

traverse :: Traversable f => Traversal (f a) (f b) a b

and the more evocative name suggests their application.

Most of the time the Traversal you will want to use is just traverse, but you can also pass any Lens or Iso as a Traversal, and composition of a Traversal (or Lens or Iso) with a Traversal (or Lens or Iso) using (.) forms a valid Traversal.

The laws for a Traversal t follow from the laws for Traversable as stated in "The Essence of the Iterator Pattern".

 t pure ≡ pure
 fmap (t f) . t g ≡ getCompose . t (Compose . fmap f . g)

One consequence of this requirement is that a Traversal needs to leave the same number of elements as a candidate for subsequent Traversal that it started with. Another testament to the strength of these laws is that the caveat expressed in section 5.5 of the "Essence of the Iterator Pattern" about exotic Traversable instances that traverse the same entry multiple times was actually already ruled out by the second law in that same paper!

type :=> a b = forall f. Applicative f => (b -> f b) -> a -> f a

This is a commonly-used infix alias for a Simple Traversal.

Lensing Traversals

element :: Traversable t => Int -> t a :-> a

Access the nth element of a Traversable container.

Attempts to access beyond the range of the Traversal will cause an error.

element ≡ elementOf traverse

elementOf :: Functor f => LensLike (ElementOf f) a b c c -> Int -> LensLike f a b c c

A Lens to 'Control.Lens.Getter.view'/'Control.Lens.Setter.set' the nth element elementOf a Traversal, Lens or Iso.

Attempts to access beyond the range of the Traversal will cause an error.

>>> [[1],[3,4]]^.elementOf (traverse.traverse) 1
3

Traversing and Lensing

traverseOf :: LensLike f a b c d -> (c -> f d) -> a -> f b

Map each element of a structure targeted by a Lens or Traversal, evaluate these actions from left to right, and collect the results.

This function is only provided for consistency, id is strictly more general.

traverseOf ≡ id

This yields the obvious law:

traverse ≡ traverseOf traverse

 traverseOf :: Iso a b c d       -> (c -> f d) -> a -> f b
 traverseOf :: Lens a b c d      -> (c -> f d) -> a -> f b
 traverseOf :: Traversal a b c d -> (c -> f d) -> a -> f b

forOf :: LensLike f a b c d -> a -> (c -> f d) -> f b

A version of traverseOf with the arguments flipped, such that:

forOf l ≡ flip (traverseOf l)

 for ≡ forOf traverse

This function is only provided for consistency, flip is strictly more general.

 forOf ≡ flip

 forOf :: Iso a b c d -> a -> (c -> f d) -> f b
 forOf :: Lens a b c d -> a -> (c -> f d) -> f b
 forOf :: Traversal a b c d -> a -> (c -> f d) -> f b

sequenceAOf :: LensLike f a b (f c) c -> a -> f b

Evaluate each action in the structure from left to right, and collect the results.

 sequenceA ≡ sequenceAOf traverse ≡ traverse id
 sequenceAOf l ≡ traverseOf l id ≡ l id

 sequenceAOf ::                  Iso a b (f c) c       -> a -> f b
 sequenceAOf ::                  Lens a b (f c) c      -> a -> f b
 sequenceAOf :: Applicative f => Traversal a b (f c) c -> a -> f b

mapMOf :: LensLike (WrappedMonad m) a b c d -> (c -> m d) -> a -> m b

Map each element of a structure targeted by a lens to a monadic action, evaluate these actions from left to right, and collect the results.

mapM ≡ mapMOf traverse

 mapMOf ::            Iso a b c d       -> (c -> m d) -> a -> m b
 mapMOf ::            Lens a b c d      -> (c -> m d) -> a -> m b
 mapMOf :: Monad m => Traversal a b c d -> (c -> m d) -> a -> m b

forMOf :: LensLike (WrappedMonad m) a b c d -> a -> (c -> m d) -> m b

forMOf is a flipped version of mapMOf, consistent with the definition of forM. forM ≡ forMOf traverse forMOf l ≡ flip (mapMOf l)

 forMOf ::            Iso a b c d       -> a -> (c -> m d) -> m b
 forMOf ::            Lens a b c d      -> a -> (c -> m d) -> m b
 forMOf :: Monad m => Traversal a b c d -> a -> (c -> m d) -> m b

sequenceOf :: LensLike (WrappedMonad m) a b (m c) c -> a -> m b

Sequence the (monadic) effects targeted by a lens in a container from left to right.

 sequence ≡ sequenceOf traverse
 sequenceOf l ≡ mapMOf l id
 sequenceOf l ≡ unwrapMonad . l WrapMonad

 sequenceOf ::            Iso a b (m c) c       -> a -> m b
 sequenceOf ::            Lens a b (m c) c      -> a -> m b
 sequenceOf :: Monad m => Traversal a b (m c) c -> a -> m b

transposeOf :: LensLike ZipList a b [c] c -> a -> [b]

This generalizes transpose to an arbitrary Traversal.

Note: transpose handles ragged inputs more intelligently, but for non-ragged inputs:

transpose ≡ transposeOf traverse

>>> transposeOf traverse [[1,2,3],[4,5,6]]
[[1,4],[2,5],[3,6]]

Since every Lens is a Traversal, we can use this as a form of monadic strength as well:

transposeOf _2 :: (b, [a]) -> [(b, a)]

mapAccumLOf :: LensLike (Backwards (State s)) a b c d -> (s -> c -> (s, d)) -> s -> a -> (s, b)

This generalizes mapAccumL to an arbitrary Traversal.

mapAccumL ≡ mapAccumLOf traverse

mapAccumLOf accumulates state from left to right.

 mapAccumLOf :: Iso a b c d       -> (s -> c -> (s, d)) -> s -> a -> (s, b)
 mapAccumLOf :: Lens a b c d      -> (s -> c -> (s, d)) -> s -> a -> (s, b)
 mapAccumLOf :: Traversal a b c d -> (s -> c -> (s, d)) -> s -> a -> (s, b)

mapAccumROf :: LensLike (State s) a b c d -> (s -> c -> (s, d)) -> s -> a -> (s, b)

This generalizes mapAccumR to an arbitrary Traversal.

mapAccumR ≡ mapAccumROf traverse

mapAccumROf accumulates state from right to left.

 mapAccumROf :: Iso a b c d       -> (s -> c -> (s, d)) -> s -> a -> (s, b)
 mapAccumROf :: Lens a b c d      -> (s -> c -> (s, d)) -> s -> a -> (s, b)
 mapAccumROf :: Traversal a b c d -> (s -> c -> (s, d)) -> s -> a -> (s, b)

scanr1Of :: LensLike (State (Maybe c)) a b c c -> (c -> c -> c) -> a -> b

This permits the use of scanr1 over an arbitrary Traversal or Lens.

scanr1 ≡ scanr1Of traverse

 scanr1Of :: Iso a b c c       -> (c -> c -> c) -> a -> b
 scanr1Of :: Lens a b c c      -> (c -> c -> c) -> a -> b
 scanr1Of :: Traversal a b c c -> (c -> c -> c) -> a -> b

scanl1Of :: LensLike (Backwards (State (Maybe c))) a b c c -> (c -> c -> c) -> a -> b

This permits the use of scanl1 over an arbitrary Traversal or Lens.

scanl1 ≡ scanl1Of traverse

 scanr1Of :: Iso a b c c       -> (c -> c -> c) -> a -> b
 scanr1Of :: Lens a b c c      -> (c -> c -> c) -> a -> b
 scanr1Of :: Traversal a b c c -> (c -> c -> c) -> a -> b

Common Traversals

class (Functor t, Foldable t) => Traversable t where

Functors representing data structures that can be traversed from left to right.

Minimal complete definition: traverse or sequenceA.

Instances are similar to Functor, e.g. given a data type

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be

 instance Traversable Tree where
    traverse f Empty = pure Empty
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

This is suitable even for abstract types, as the laws for <*> imply a form of associativity.

The superclass instances should satisfy the following:

• In the Functor instance, fmap should be equivalent to traversal with the identity applicative functor (fmapDefault).
• In the Foldable instance, foldMap should be equivalent to traversal with a constant applicative functor (foldMapDefault).

Methods

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Map each element of a structure to an action, evaluate these actions from left to right, and collect the results.

Instances

Traversable []

Traversable Maybe

Traversable Identity

Traversable Digit

Traversable Node

Traversable Elem

Traversable FingerTree

Traversable Tree

Traversable Seq

Traversable ViewL

Traversable ViewR

Traversable IntMap

Traversable NonEmpty

Traversable Level

(Functor (Array i), Foldable (Array i), Ix i) => Traversable (Array i)

(Functor (IdentityT f), Foldable (IdentityT f), Traversable f) => Traversable (IdentityT f)

(Functor (Map k), Foldable (Map k)) => Traversable (Map k)

(Functor (ListT f), Foldable (ListT f), Traversable f) => Traversable (ListT f)

(Functor (Backwards f), Foldable (Backwards f), Traversable f) => Traversable (Backwards f)

Derived instance.

(Functor (MaybeT f), Foldable (MaybeT f), Traversable f) => Traversable (MaybeT f)

(Functor (HashMap k), Foldable (HashMap k)) => Traversable (HashMap k)

(Functor (EnvT e w), Foldable (EnvT e w), Traversable w) => Traversable (EnvT e w)

(Functor (ErrorT e f), Foldable (ErrorT e f), Traversable f) => Traversable (ErrorT e f)

(Functor (WriterT w f), Foldable (WriterT w f), Traversable f) => Traversable (WriterT w f)

(Functor (WriterT w f), Foldable (WriterT w f), Traversable f) => Traversable (WriterT w f)

(Functor (Compose f g), Foldable (Compose f g), Traversable f, Traversable g) => Traversable (Compose f g)

ignored :: Traversal a a c d

This is the trivial empty traversal.

ignored :: Applicative f => (c -> f d) -> a -> f a

ignored ≡ const pure

traverseLeft :: Traversal (Either a c) (Either b c) a b

A traversal for tweaking the left-hand value of an Either:

>>> over traverseLeft (+1) (Left 2)
Left 3
>>> over traverseLeft (+1) (Right 2)
Right 2
>>> Right 42 ^.traverseLeft :: String
""
>>> Left "hello" ^.traverseLeft
"hello"

traverseLeft :: Applicative f => (a -> f b) -> Either a c -> f (Either b c)

traverseRight :: Traversal (Either c a) (Either c b) a b

traverse the right-hand value of an Either:

traverseRight ≡ traverse

Unfortunately the instance for Traversable (Either c) is still missing from base, so this can't just be traverse

>>> over traverseRight (+1) (Left 2)
Left 2
>>> over traverseRight (+1) (Right 2)
Right 3
>>> Right "hello" ^.traverseRight
"hello"
>>> Left "hello" ^.traverseRight :: [Double]
[]

traverseRight :: Applicative f => (a -> f b) -> Either c a -> f (Either c a)

both :: Traversal (a, a) (b, b) a b

Traverse both parts of a tuple with matching types.

>>> both *~ 10 $ (1,2)
(10,20)
>>> over both length ("hello","world")
(5,5)
>>> ("hello","world")^.both
"helloworld"

Cloning Traversals

cloneTraversal :: Applicative f => ((c -> Bazaar c d d) -> a -> Bazaar c d b) -> (c -> f d) -> a -> f b

A Traversal is completely characterized by its behavior on a Bazaar.

Cloning a Traversal is one way to make sure you arent given something weaker, such as a Fold and can be used as a way to pass around traversals that have to be monomorphic in f.

Note: This only accepts a proper Traversal (or Lens). To clone a Lens as such, use cloneLens

Note: It is usually better to ReifyTraversal and use reflectTraversal than to cloneTraversal. The former can execute at full speed, while the latter needs to round trip through the Bazaar.

>>> let foo l a = (view (cloneTraversal l) a, set (cloneTraversal l) 10 a)
>>> foo both ("hello","world")
("helloworld",(10,10))

cloneTraversal :: LensLike (Bazaar c d) a b c d -> Traversal a b c d

data ReifiedTraversal a b c d

A form of Traversal that can be stored monomorphically in a container.

Constructors

ReifyTraversal

Fields

reflectTraversal :: Traversal a b c d

Simple

type SimpleTraversal a b = Traversal a a b b

type SimpleTraversal = Simple Traversal

type SimpleReifiedTraversal a b = ReifiedTraversal a a b b

type SimpleReifiedTraversal = Simple ReifiedTraversal