| 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.Traversal
Description
A is a generalization of Traversal s t a btraverse from
Traversable. It allows you to traverse over a structure and change out
its contents with monadic or Applicative side-effects. Starting from
traverse:: (Traversablet,Applicativef) => (a -> f b) -> t a -> f (t b)
we monomorphize the contents and result to obtain
typeTraversals t a b = forall f.Applicativef => (a -> f b) -> s -> f t
A Traversal can be used as a Fold.
Any Traversal can be used for Getting like a Fold,
because given a Monoid m, we have an Applicative for
(. Everything you know how to do with a Const m)Traversable container,
you can with a Traversal, and here we provide combinators that generalize
the usual Traversable operations.
Synopsis
- type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t
- type Traversal' s a = Traversal s s a a
- type ATraversal s t a b = LensLike (Bazaar (->) a b) s t a b
- type ATraversal' s a = ATraversal s s a a
- type ATraversal1 s t a b = LensLike (Bazaar1 (->) a b) s t a b
- type ATraversal1' s a = ATraversal1 s s a a
- traverseOf :: LensLike f s t a b -> (a -> f b) -> s -> f t
- forOf :: LensLike f s t a b -> s -> (a -> f b) -> f t
- sequenceAOf :: LensLike f s t (f b) b -> s -> f t
- mapMOf :: LensLike (WrappedMonad m) s t a b -> (a -> m b) -> s -> m t
- forMOf :: LensLike (WrappedMonad m) s t a b -> s -> (a -> m b) -> m t
- sequenceOf :: LensLike (WrappedMonad m) s t (m b) b -> s -> m t
- transposeOf :: LensLike ZipList s t [a] a -> s -> [t]
- mapAccumLOf :: LensLike (State acc) 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)
- scanr1Of :: LensLike (Backwards (State (Maybe a))) s t a a -> (a -> a -> a) -> s -> t
- scanl1Of :: LensLike (State (Maybe a)) s t a a -> (a -> a -> a) -> s -> t
- failover :: Alternative m => LensLike ((,) Any) s t a b -> (a -> b) -> s -> m t
- class (Functor t, Foldable t) => Traversable (t :: Type -> Type) where
- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
- ignored :: Applicative f => pafb -> s -> f s
- both :: Bitraversable r => Traversal (r a a) (r b b) a b
- newtype Bazaar p a b t = Bazaar {
- runBazaar :: forall f. Applicative f => p a (f b) -> f t
- type Bazaar' p a = Bazaar p a a
- newtype Bazaar1 p a b t = Bazaar1 {
- runBazaar1 :: forall f. Applicative f => p a (f b) -> f t
- type Bazaar1' p a = Bazaar1 p a a
Traversals
type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t Source #
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::Traversablef =>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".
tpure≡purefmap(t f).t g ≡getCompose.t (Compose.fmapf.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 Traversal' s a = Traversal s s a a Source #
typeTraversal'=SimpleTraversal
type ATraversal s t a b = LensLike (Bazaar (->) a b) s t a b Source #
When you see this as an argument to a function, it expects a Traversal.
type ATraversal' s a = ATraversal s s a a Source #
typeATraversal'=SimpleATraversal
type ATraversal1 s t a b = LensLike (Bazaar1 (->) a b) s t a b Source #
When you see this as an argument to a function, it expects a Traversal1.
type ATraversal1' s a = ATraversal1 s s a a Source #
typeATraversal1'=SimpleATraversal1
Traversing and Lensing
traverseOf :: LensLike f s t a b -> (a -> f b) -> s -> f t Source #
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 each print (1,2,3)1 2 3 ((),(),())
traverseOf≡iditraverseOfl ≡traverseOfl.IndexeditraverseOfitraversed≡itraverse
This yields the obvious law:
traverse≡traverseOftraverse
traverseOf::Functorf =>Isos t a b -> (a -> f b) -> s -> f ttraverseOf::Functorf =>Lenss t a b -> (a -> f b) -> s -> f ttraverseOf::Applyf =>Traversal1s t a b -> (a -> f b) -> s -> f ttraverseOf::Applicativef =>Traversals t a b -> (a -> f b) -> s -> f t
forOf :: LensLike f s t a b -> s -> (a -> f b) -> f t Source #
A version of traverseOf with the arguments flipped, such that:
>>>forOf each (1,2,3) print1 2 3 ((),(),())
This function is only provided for consistency, flip is strictly more general.
forOf≡flipforOf≡flip.traverseOf
for≡forOftraverseiforl s ≡forl s.Indexed
forOf::Functorf =>Isos t a b -> s -> (a -> f b) -> f tforOf::Functorf =>Lenss t a b -> s -> (a -> f b) -> f tforOf::Applicativef =>Traversals t a b -> s -> (a -> f b) -> f t
sequenceAOf :: LensLike f s t (f b) b -> s -> f t Source #
Evaluate each action in the structure from left to right, and collect the results.
>>>sequenceAOf both ([1,2],[3,4])[(1,3),(1,4),(2,3),(2,4)]
sequenceA≡sequenceAOftraverse≡traverseidsequenceAOfl ≡traverseOflid≡ lid
sequenceAOf::Functorf =>Isos t (f b) b -> s -> f tsequenceAOf::Functorf =>Lenss t (f b) b -> s -> f tsequenceAOf::Applicativef =>Traversals t (f b) b -> s -> f t
mapMOf :: LensLike (WrappedMonad m) s t a b -> (a -> m b) -> s -> m t Source #
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.
>>>mapMOf both (\x -> [x, x + 1]) (1,3)[(1,3),(1,4),(2,3),(2,4)]
mapM≡mapMOftraverseimapMOfl ≡forMl.Indexed
mapMOf::Monadm =>Isos t a b -> (a -> m b) -> s -> m tmapMOf::Monadm =>Lenss t a b -> (a -> m b) -> s -> m tmapMOf::Monadm =>Traversals t a b -> (a -> m b) -> s -> m t
forMOf :: LensLike (WrappedMonad m) s t a b -> s -> (a -> m b) -> m t Source #
forMOf is a flipped version of mapMOf, consistent with the definition of forM.
>>>forMOf both (1,3) $ \x -> [x, x + 1][(1,3),(1,4),(2,3),(2,4)]
forM≡forMOftraverseforMOfl ≡flip(mapMOfl)iforMOfl s ≡forMl s.Indexed
forMOf::Monadm =>Isos t a b -> s -> (a -> m b) -> m tforMOf::Monadm =>Lenss t a b -> s -> (a -> m b) -> m tforMOf::Monadm =>Traversals t a b -> s -> (a -> m b) -> m t
sequenceOf :: LensLike (WrappedMonad m) s t (m b) b -> s -> m t Source #
Sequence the (monadic) effects targeted by a Lens in a container from left to right.
>>>sequenceOf each ([1,2],[3,4],[5,6])[(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)]
sequence≡sequenceOftraversesequenceOfl ≡mapMOflidsequenceOfl ≡unwrapMonad.lWrapMonad
sequenceOf::Monadm =>Isos t (m b) b -> s -> m tsequenceOf::Monadm =>Lenss t (m b) b -> s -> m tsequenceOf::Monadm =>Traversals 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:
>>>transposeOf traverse [[1,2,3],[4,5,6]][[1,4],[2,5],[3,6]]
transpose≡transposeOftraverse
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.
mapAccumL≡mapAccumLOftraverse
mapAccumLOf accumulates State from left to right.
mapAccumLOf::Isos t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)mapAccumLOf::Lenss t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)mapAccumLOf::Traversals t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumLOf::LensLike(Stateacc) s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)mapAccumLOfl f acc0 s =swap(runState(l (a ->state(acc ->swap(f acc a))) s) acc0)
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.
mapAccumR≡mapAccumROftraverse
mapAccumROf accumulates State from right to left.
mapAccumROf::Isos t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)mapAccumROf::Lenss t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)mapAccumROf::Traversals t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
mapAccumROf::LensLike(Backwards(Stateacc)) s t a b -> (acc -> a -> (acc, b)) -> acc -> s -> (acc, t)
failover :: Alternative m => LensLike ((,) Any) s t a b -> (a -> b) -> s -> m t Source #
Try to map a function over this Traversal, failing if the Traversal has no targets.
>>>failover (element 3) (*2) [1,2] :: Maybe [Int]Nothing
>>>failover _Left (*2) (Right 4) :: Maybe (Either Int Int)Nothing
>>>failover _Right (*2) (Right 4) :: Maybe (Either Int Int)Just (Right 8)
failover :: Alternative m => Traversal s t a b -> (a -> b) -> s -> m t
Parts and Holes
Common Traversals
class (Functor t, Foldable t) => Traversable (t :: Type -> Type) where #
Functors representing data structures that can be traversed from left to right.
A definition of traverse must satisfy the following laws:
- naturality
t .for every applicative transformationtraversef =traverse(t . f)t- identity
traverseIdentity = Identity- composition
traverse(Compose .fmapg . f) = Compose .fmap(traverseg) .traversef
A definition of sequenceA must satisfy the following laws:
- naturality
t .for every applicative transformationsequenceA=sequenceA.fmaptt- identity
sequenceA.fmapIdentity = Identity- composition
sequenceA.fmapCompose = Compose .fmapsequenceA.sequenceA
where an applicative transformation is a function
t :: (Applicative f, Applicative g) => f a -> g a
preserving the Applicative operations, i.e.
and the identity functor Identity and composition of functors Compose
are defined as
newtype Identity a = Identity a
instance Functor Identity where
fmap f (Identity x) = Identity (f x)
instance Applicative Identity where
pure x = Identity x
Identity f <*> Identity x = Identity (f x)
newtype Compose f g a = Compose (f (g a))
instance (Functor f, Functor g) => Functor (Compose f g) where
fmap f (Compose x) = Compose (fmap (fmap f) x)
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
pure x = Compose (pure (pure x))
Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)(The naturality law is implied by parametricity.)
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
Functorinstance,fmapshould be equivalent to traversal with the identity applicative functor (fmapDefault). - In the
Foldableinstance,foldMapshould 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. For a version that ignores
the results see traverse_.
Instances
ignored :: Applicative f => pafb -> s -> f s Source #
both :: Bitraversable r => Traversal (r a a) (r b b) a b Source #
Traverse both parts of a Bitraversable container with matching types.
Usually that type will be a pair. Use each to traverse
the elements of arbitrary homogeneous tuples.
>>>(1,2) & both *~ 10(10,20)
>>>over both length ("hello","world")(5,5)
>>>("hello","world")^.both"helloworld"
both::Traversal(a, a) (b, b) a bboth::Traversal(Eithera a) (Eitherb b) a b
Implementation Details
newtype Bazaar p 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.
http://twanvl.nl/blog/haskell/non-regular1
A Bazaar is like a Traversal that has already been applied to some structure.
Where a holds an Context a b ta and a function from b to
t, a holds Bazaar a b tN as and a function from N
bs to t, (where N might be infinite).
Mnemonically, a Bazaar holds many stores and you can easily add more.
This is a final encoding of Bazaar.
Constructors
| Bazaar | |
Fields
| |
Instances
| Profunctor p => Bizarre p (Bazaar p) Source # | |
Defined in Control.Lens.Internal.Bazaar Methods bazaar :: Applicative f => p a (f b) -> Bazaar p a b t -> f t Source # | |
| IndexedFunctor (Bazaar p) Source # | |
| Functor (Bazaar p a b) Source # | |
| Applicative (Bazaar p a b) Source # | |
Defined in Control.Lens.Internal.Bazaar Methods pure :: a0 -> Bazaar p a b a0 # (<*>) :: Bazaar p a b (a0 -> b0) -> Bazaar p a b a0 -> Bazaar p a b b0 # liftA2 :: (a0 -> b0 -> c) -> Bazaar p a b a0 -> Bazaar p a b b0 -> Bazaar p a b c # (*>) :: Bazaar p a b a0 -> Bazaar p a b b0 -> Bazaar p a b b0 # (<*) :: Bazaar p a b a0 -> Bazaar p a b b0 -> Bazaar p a b a0 # | |
newtype Bazaar1 p 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.
http://twanvl.nl/blog/haskell/non-regular1
A Bazaar1 is like a Traversal that has already been applied to some structure.
Where a holds an Context a b ta and a function from b to
t, a holds Bazaar1 a b tN as and a function from N
bs to t, (where N might be infinite).
Mnemonically, a Bazaar1 holds many stores and you can easily add more.
This is a final encoding of Bazaar1.
Constructors
| Bazaar1 | |
Fields
| |
Instances
| Profunctor p => Bizarre1 p (Bazaar1 p) Source # | |
Defined in Control.Lens.Internal.Bazaar Methods bazaar1 :: Applicative f => p a (f b) -> Bazaar1 p a b t -> f t Source # | |
| IndexedFunctor (Bazaar1 p) Source # | |
| Functor (Bazaar1 p a b) Source # | |