lens-3.7.0.1: Lenses, Folds and Traversals

Portability Rank2Types provisional Edward Kmett None

Control.Lens.Traversal

Description

A Traversal s t a b 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) => (a -> f b) -> t a -> f (t b)

we monomorphize the contents and result to obtain

type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t

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.

Synopsis

# Lenses

type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f tSource

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 purepure
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!

# Traversing and Lensing

traverseOf :: LensLike f s t a b -> (a -> f b) -> s -> f tSource

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.

traverseOfid

This yields the obvious law:

traversetraverseOf traverse
traverseOf :: Iso s t a b       -> (a -> f b) -> s -> f t
traverseOf :: Lens s t a b      -> (a -> f b) -> s -> f t
traverseOf :: Traversal s t a b -> (a -> f b) -> s -> f t

forOf :: LensLike f s t a b -> s -> (a -> f b) -> f tSource

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

forOf l ≡ flip (traverseOf l)
forforOf traverse

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

forOfflip
forOf :: Iso s t a b -> s -> (a -> f b) -> f t
forOf :: Lens s t a b -> s -> (a -> f b) -> f t
forOf :: Traversal s t a b -> s -> (a -> f b) -> f t

sequenceAOf :: LensLike f s t (f b) b -> s -> f tSource

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

sequenceAsequenceAOf traversetraverse id
sequenceAOf l ≡ traverseOf l id ≡ l id
sequenceAOf ::                  Iso s t (f b) b       -> s -> f t
sequenceAOf ::                  Lens s t (f b) b      -> s -> f t
sequenceAOf :: Applicative f => Traversal s t (f b) b -> s -> f t

mapMOf :: LensLike (WrappedMonad m) s t a b -> (a -> m b) -> s -> m tSource

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.

mapMmapMOf traverse
mapMOf ::            Iso s t a b       -> (a -> m b) -> s -> m t
mapMOf ::            Lens s t a b      -> (a -> m b) -> s -> m t
mapMOf :: Monad m => Traversal s t a b -> (a -> m b) -> s -> m t

forMOf :: LensLike (WrappedMonad m) s t a b -> s -> (a -> m b) -> m tSource

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

forMOf ::            Iso s t a b       -> s -> (a -> m b) -> m t
forMOf ::            Lens s t a b      -> s -> (a -> m b) -> m t
forMOf :: Monad m => Traversal s t a b -> s -> (a -> m b) -> m t

sequenceOf :: LensLike (WrappedMonad m) s t (m b) b -> s -> m tSource

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

sequencesequenceOf traverse
sequenceOf l ≡ mapMOf l id
sequenceOf ::            Iso s t (m b) b       -> s -> m t
sequenceOf ::            Lens s t (m b) b      -> s -> m t
sequenceOf :: Monad m => Traversal s t (m b) b -> s -> m t

transposeOf :: LensLike ZipList s t [a] a -> s -> [t]Source

This generalizes transpose to an arbitrary Traversal.

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

transposetransposeOf 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 (State acc) s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)Source

This generalizes mapAccumL to an arbitrary Traversal.

mapAccumLmapAccumLOf traverse

mapAccumLOf accumulates state from left to right.

mapAccumLOf :: Iso s t a b       -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumLOf :: Lens s t a b      -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumLOf :: Traversal s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)

mapAccumROf :: LensLike (Backwards (State acc)) s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)Source

This generalizes mapAccumR to an arbitrary Traversal.

mapAccumRmapAccumROf traverse

mapAccumROf accumulates state from right to left.

mapAccumROf :: Iso s t a b       -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumROf :: Lens s t a b      -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumROf :: Traversal s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)

scanr1Of :: LensLike (Backwards (State (Maybe a))) s t a a -> (a -> a -> a) -> s -> tSource

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

scanr1scanr1Of traverse
scanr1Of :: Iso s t a a       -> (a -> a -> a) -> s -> t
scanr1Of :: Lens s t a a      -> (a -> a -> a) -> s -> t
scanr1Of :: Traversal s t a a -> (a -> a -> a) -> s -> t

scanl1Of :: LensLike (State (Maybe a)) s t a a -> (a -> a -> a) -> s -> tSource

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

scanl1scanl1Of traverse
scanr1Of :: Iso s t a a       -> (a -> a -> a) -> s -> t
scanr1Of :: Lens s t a a      -> (a -> a -> a) -> s -> t
scanr1Of :: Traversal s t a a -> (a -> a -> a) -> s -> t

# Parts and Holes

partsOf :: Functor f => LensLike (BazaarT a a f) s t a a -> LensLike f s t [a] [a]Source

partsOf turns a Traversal into a Lens that resembles an early version of the uniplate (or biplate) type.

Note: You should really try to maintain the invariant of the number of children in the list.

Any extras will be lost. If you do not supply enough, then the remainder will come from the original structure.

So technically, this is only a lens if you do not change the number of results it returns.

When applied to a Fold the result is merely a Getter.

partsOf :: Simple Iso s a       -> Simple Lens s [a]
partsOf :: Simple Lens s a      -> Simple Lens s [a]
partsOf :: Simple Traversal s a -> Simple Lens s [a]
partsOf :: Fold s a             -> Getter s [a]
partsOf :: Getter s a           -> Getter s [a]

partsOf' :: LensLike (Bazaar a a) s t a a -> Lens s t [a] [a]Source

A type-restricted version of partsOf that can only be used with a Traversal.

unsafePartsOf :: Functor f => LensLike (BazaarT a b f) s t a b -> LensLike f s t [a] [b]Source

unsafePartsOf turns a Traversal into a uniplate (or biplate) family.

If you do not need the types of s and t to be different, it is recommended that you use partsOf

It is generally safer to traverse with the Bazaar rather than use this combinator. However, it is sometimes convenient.

This is unsafe because if you don't supply at least as many b's as you were given a's, then the reconstruction of t will result in an error!

When applied to a Fold the result is merely a Getter (and becomes safe).

unsafePartsOf :: Iso s t a b       -> Lens s t [a] [b]
unsafePartsOf :: Lens s t a b      -> Lens s t [a] [b]
unsafePartsOf :: Traversal s t a b -> Lens s t [a] [b]
unsafePartsOf :: Fold s a          -> Getter s [a]
unsafePartsOf :: Getter s a        -> Getter s [a]

unsafePartsOf' :: LensLike (Bazaar a b) s t a b -> Lens s t [a] [b]Source

holesOf :: LensLike (Bazaar a a) s t a a -> s -> [Context a a t]Source

The one-level version of contextsOf. This extracts a list of the immediate children according to a given Traversal as editable contexts.

Given a context you can use pos to see the values, peek at what the structure would be like with an edited result, or simply extract the original structure.

propChildren l x = childrenOf l x == map pos (holesOf l x)
propId l x = all (== x) [extract w | w <- holesOf l x]
holesOf :: Simple Iso s a       -> s -> [Context a a s]
holesOf :: Simple Lens s a      -> s -> [Context a a s]
holesOf :: Simple Traversal s a -> s -> [Context a a s]

singular :: Functor f => LensLike (BazaarT a a f) s t a a -> LensLike f s t a aSource

This converts a Traversal that you know will target one or more elements to a Lens. It can also be used to transform a non-empty Fold into a Getter or a non-empty MonadicFold into an Action.

The resulting Lens, Getter, or Action will be partial if the supplied traversal returns no results.

singular :: Traversal s t a a -> Lens s t a a
singular :: Fold s a          -> Getter s a
singular :: MonadicFold m s a -> Action m s a

unsafeSingular :: Functor f => LensLike (BazaarT a b f) s t a b -> LensLike f s t a bSource

This converts a Traversal that you know will target only one element to a Lens. It can also be used to transform a Fold into a Getter or a MonadicFold into an Action.

The resulting Lens, Getter, or Action will be partial if the Traversal targets nothing or more than one element.

unsafeSingular :: Traversal s t a b -> Lens s t a b
unsafeSingular :: Fold s a          -> Getter s a
unsafeSingular :: MonadicFold m s a -> Action m s a

# 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:

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 Vector (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 (Reverse f), Foldable (Reverse f), Traversable f) => Traversable (Reverse f) Traverse from right to left. (Functor (Backwards f), Foldable (Backwards f), Traversable f) => Traversable (Backwards f) Derived instance. (Functor (Lift f), Foldable (Lift f), Traversable f) => Traversable (Lift f) (Functor (Constant a), Foldable (Constant a)) => Traversable (Constant a) (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 (Coproduct f g), Foldable (Coproduct f g), Traversable f, Traversable g) => Traversable (Coproduct f g) (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)

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

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"

beside :: Applicative f => LensLike f s t a b -> LensLike f s' t' a b -> LensLike f (s, s') (t, t') a bSource

Apply a different Traversal or Fold to each side of a tuple.

>>> ("hello",["world","!!!"])^..beside id traverse
["hello","world","!!!"]

taking :: Applicative f => Int -> SimpleLensLike (BazaarT a a f) s a -> SimpleLensLike f s aSource

Visit the first n targets of a Traversal, Fold, Getter or Lens.

>>> [("hello","world"),("!!!","!!!")]^.. taking 2 (traverse.both)
["hello","world"]
>>> [1..] ^.. taking 3 traverse
[1,2,3]
>>> over (taking 5 traverse) succ "hello world"
"ifmmp world"

dropping :: Applicative f => Int -> SimpleLensLike (Indexing f) s a -> SimpleLensLike f s aSource

Visit all but the first n targets of a Traversal, Fold, Getter or Lens.

>>> ("hello","world") ^? dropping 1 both
Just "world"

Dropping works on infinite traversals as well:

>>> [1..]^? dropping 1 folded
Just 2

loci :: Traversal (Bazaar a c s) (Bazaar b c s) a bSource

This Traversal allows you to traverse the individual stores in a Bazaar.

# Cloning Traversals

cloneTraversal :: Applicative f => ((a -> Bazaar a b b) -> s -> Bazaar a b t) -> (a -> f b) -> s -> f tSource

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

Cloning a Traversal is one way to make sure you aren't 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 a b) s t a b -> Traversal s t a b

data ReifiedTraversal s t a b Source

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

Constructors

 ReifyTraversal FieldsreflectTraversal :: Traversal s t a b

# Simple

type SimpleTraversal s a = Traversal s s a aSource

type SimpleTraversal = Simple Traversal

type SimpleReifiedTraversal s a = ReifiedTraversal s s a aSource

type SimpleReifiedTraversal = Simple ReifiedTraversal

# Exposed Implementation Details

newtype Bazaar a b t Source

This is used to characterize a Traversal.

a.k.a. indexed Cartesian store comonad, indexed Kleene store comonad, or an indexed FunList.

Bazaar a b t is isomorphic to data Bazaar a b t = Buy t | Trade (Bazaar a b (b -> t)) a, and to exists s. (s, Traversal s t a b).

A Bazaar is like a Traversal that has already been applied to some structure.

Where a Context a b t holds an a and a function from b to t, a Bazaar a b t holds N as and a function from N bs to t.

Mnemonically, a Bazaar holds many stores and you can easily add more.

This is a final encoding of Bazaar.

Constructors

 Bazaar FieldsrunBazaar :: forall f. Applicative f => (a -> f b) -> f t

Instances

 Functor (Bazaar a b) Functor (Bazaar a b) => Applicative (Bazaar a b) (Functor (Bazaar a b), ~ * a b) => Comonad (Bazaar a b) (Comonad (Bazaar a b), ~ * a b) => ComonadApply (Bazaar a b)