W3cubDocs

/Haskell 8

Data.Traversable

Copyright Conor McBride and Ross Paterson 2005
License BSD-style (see the LICENSE file in the distribution)
Maintainer [email protected]
Stability experimental
Portability portable
Safe Haskell Trustworthy
Language Haskell2010

Description

Class of data structures that can be traversed from left to right, performing an action on each element.

See also

The Traversable class

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

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

A definition of traverse must satisfy the following laws:

naturality
t . traverse f = traverse (t . f) for every applicative transformation t
identity
traverse Identity = Identity
composition
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

A definition of sequenceA must satisfy the following laws:

naturality
t . sequenceA = sequenceA . fmap t for every applicative transformation t
identity
sequenceA . fmap Identity = Identity
composition
sequenceA . fmap Compose = Compose . fmap sequenceA . 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:

Minimal complete definition

traverse | sequenceA

Methods

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

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

sequenceA :: Applicative f => t (f a) -> f (t a) Source

Evaluate each action in the structure from left to right, and collect the results. For a version that ignores the results see sequenceA_.

mapM :: Monad m => (a -> m b) -> t a -> m (t b) Source

Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results. For a version that ignores the results see mapM_.

sequence :: Monad m => t (m a) -> m (t a) Source

Evaluate each monadic action in the structure from left to right, and collect the results. For a version that ignores the results see sequence_.

Instances
Traversable []

Since: base-2.1

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> [a] -> f [b] Source

sequenceA :: Applicative f => [f a] -> f [a] Source

mapM :: Monad m => (a -> m b) -> [a] -> m [b] Source

sequence :: Monad m => [m a] -> m [a] Source

Traversable Maybe

Since: base-2.1

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Maybe a -> f (Maybe b) Source

sequenceA :: Applicative f => Maybe (f a) -> f (Maybe a) Source

mapM :: Monad m => (a -> m b) -> Maybe a -> m (Maybe b) Source

sequence :: Monad m => Maybe (m a) -> m (Maybe a) Source

Traversable Par1

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Par1 a -> f (Par1 b) Source

sequenceA :: Applicative f => Par1 (f a) -> f (Par1 a) Source

mapM :: Monad m => (a -> m b) -> Par1 a -> m (Par1 b) Source

sequence :: Monad m => Par1 (m a) -> m (Par1 a) Source

Traversable NonEmpty

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> NonEmpty a -> f (NonEmpty b) Source

sequenceA :: Applicative f => NonEmpty (f a) -> f (NonEmpty a) Source

mapM :: Monad m => (a -> m b) -> NonEmpty a -> m (NonEmpty b) Source

sequence :: Monad m => NonEmpty (m a) -> m (NonEmpty a) Source

Traversable Down

Since: base-4.12.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Down a -> f (Down b) Source

sequenceA :: Applicative f => Down (f a) -> f (Down a) Source

mapM :: Monad m => (a -> m b) -> Down a -> m (Down b) Source

sequence :: Monad m => Down (m a) -> m (Down a) Source

Traversable Product

Since: base-4.8.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Product a -> f (Product b) Source

sequenceA :: Applicative f => Product (f a) -> f (Product a) Source

mapM :: Monad m => (a -> m b) -> Product a -> m (Product b) Source

sequence :: Monad m => Product (m a) -> m (Product a) Source

Traversable Sum

Since: base-4.8.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Sum a -> f (Sum b) Source

sequenceA :: Applicative f => Sum (f a) -> f (Sum a) Source

mapM :: Monad m => (a -> m b) -> Sum a -> m (Sum b) Source

sequence :: Monad m => Sum (m a) -> m (Sum a) Source

Traversable Dual

Since: base-4.8.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Dual a -> f (Dual b) Source

sequenceA :: Applicative f => Dual (f a) -> f (Dual a) Source

mapM :: Monad m => (a -> m b) -> Dual a -> m (Dual b) Source

sequence :: Monad m => Dual (m a) -> m (Dual a) Source

Traversable Last

Since: base-4.8.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Last a -> f (Last b) Source

sequenceA :: Applicative f => Last (f a) -> f (Last a) Source

mapM :: Monad m => (a -> m b) -> Last a -> m (Last b) Source

sequence :: Monad m => Last (m a) -> m (Last a) Source

Traversable First

Since: base-4.8.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> First a -> f (First b) Source

sequenceA :: Applicative f => First (f a) -> f (First a) Source

mapM :: Monad m => (a -> m b) -> First a -> m (First b) Source

sequence :: Monad m => First (m a) -> m (First a) Source

Traversable Identity

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Identity a -> f (Identity b) Source

sequenceA :: Applicative f => Identity (f a) -> f (Identity a) Source

mapM :: Monad m => (a -> m b) -> Identity a -> m (Identity b) Source

sequence :: Monad m => Identity (m a) -> m (Identity a) Source

Traversable ZipList

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> ZipList a -> f (ZipList b) Source

sequenceA :: Applicative f => ZipList (f a) -> f (ZipList a) Source

mapM :: Monad m => (a -> m b) -> ZipList a -> m (ZipList b) Source

sequence :: Monad m => ZipList (m a) -> m (ZipList a) Source

Traversable Option

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a -> f b) -> Option a -> f (Option b) Source

sequenceA :: Applicative f => Option (f a) -> f (Option a) Source

mapM :: Monad m => (a -> m b) -> Option a -> m (Option b) Source

sequence :: Monad m => Option (m a) -> m (Option a) Source

Traversable Last

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a -> f b) -> Last a -> f (Last b) Source

sequenceA :: Applicative f => Last (f a) -> f (Last a) Source

mapM :: Monad m => (a -> m b) -> Last a -> m (Last b) Source

sequence :: Monad m => Last (m a) -> m (Last a) Source

Traversable First

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a -> f b) -> First a -> f (First b) Source

sequenceA :: Applicative f => First (f a) -> f (First a) Source

mapM :: Monad m => (a -> m b) -> First a -> m (First b) Source

sequence :: Monad m => First (m a) -> m (First a) Source

Traversable Max

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a -> f b) -> Max a -> f (Max b) Source

sequenceA :: Applicative f => Max (f a) -> f (Max a) Source

mapM :: Monad m => (a -> m b) -> Max a -> m (Max b) Source

sequence :: Monad m => Max (m a) -> m (Max a) Source

Traversable Min

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a -> f b) -> Min a -> f (Min b) Source

sequenceA :: Applicative f => Min (f a) -> f (Min a) Source

mapM :: Monad m => (a -> m b) -> Min a -> m (Min b) Source

sequence :: Monad m => Min (m a) -> m (Min a) Source

Traversable Complex

Since: base-4.9.0.0

Instance details

Defined in Data.Complex

Methods

traverse :: Applicative f => (a -> f b) -> Complex a -> f (Complex b) Source

sequenceA :: Applicative f => Complex (f a) -> f (Complex a) Source

mapM :: Monad m => (a -> m b) -> Complex a -> m (Complex b) Source

sequence :: Monad m => Complex (m a) -> m (Complex a) Source

Traversable (Either a)

Since: base-4.7.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a0 -> f b) -> Either a a0 -> f (Either a b) Source

sequenceA :: Applicative f => Either a (f a0) -> f (Either a a0) Source

mapM :: Monad m => (a0 -> m b) -> Either a a0 -> m (Either a b) Source

sequence :: Monad m => Either a (m a0) -> m (Either a a0) Source

Traversable (V1 :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> V1 a -> f (V1 b) Source

sequenceA :: Applicative f => V1 (f a) -> f (V1 a) Source

mapM :: Monad m => (a -> m b) -> V1 a -> m (V1 b) Source

sequence :: Monad m => V1 (m a) -> m (V1 a) Source

Traversable (U1 :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> U1 a -> f (U1 b) Source

sequenceA :: Applicative f => U1 (f a) -> f (U1 a) Source

mapM :: Monad m => (a -> m b) -> U1 a -> m (U1 b) Source

sequence :: Monad m => U1 (m a) -> m (U1 a) Source

Traversable ((,) a)

Since: base-4.7.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a0 -> f b) -> (a, a0) -> f (a, b) Source

sequenceA :: Applicative f => (a, f a0) -> f (a, a0) Source

mapM :: Monad m => (a0 -> m b) -> (a, a0) -> m (a, b) Source

sequence :: Monad m => (a, m a0) -> m (a, a0) Source

Traversable (Proxy :: Type -> Type)

Since: base-4.7.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Proxy a -> f (Proxy b) Source

sequenceA :: Applicative f => Proxy (f a) -> f (Proxy a) Source

mapM :: Monad m => (a -> m b) -> Proxy a -> m (Proxy b) Source

sequence :: Monad m => Proxy (m a) -> m (Proxy a) Source

Traversable (Arg a)

Since: base-4.9.0.0

Instance details

Defined in Data.Semigroup

Methods

traverse :: Applicative f => (a0 -> f b) -> Arg a a0 -> f (Arg a b) Source

sequenceA :: Applicative f => Arg a (f a0) -> f (Arg a a0) Source

mapM :: Monad m => (a0 -> m b) -> Arg a a0 -> m (Arg a b) Source

sequence :: Monad m => Arg a (m a0) -> m (Arg a a0) Source

Traversable f => Traversable (Rec1 f)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Rec1 f a -> f0 (Rec1 f b) Source

sequenceA :: Applicative f0 => Rec1 f (f0 a) -> f0 (Rec1 f a) Source

mapM :: Monad m => (a -> m b) -> Rec1 f a -> m (Rec1 f b) Source

sequence :: Monad m => Rec1 f (m a) -> m (Rec1 f a) Source

Traversable (URec Char :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec Char a -> f (URec Char b) Source

sequenceA :: Applicative f => URec Char (f a) -> f (URec Char a) Source

mapM :: Monad m => (a -> m b) -> URec Char a -> m (URec Char b) Source

sequence :: Monad m => URec Char (m a) -> m (URec Char a) Source

Traversable (URec Double :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec Double a -> f (URec Double b) Source

sequenceA :: Applicative f => URec Double (f a) -> f (URec Double a) Source

mapM :: Monad m => (a -> m b) -> URec Double a -> m (URec Double b) Source

sequence :: Monad m => URec Double (m a) -> m (URec Double a) Source

Traversable (URec Float :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec Float a -> f (URec Float b) Source

sequenceA :: Applicative f => URec Float (f a) -> f (URec Float a) Source

mapM :: Monad m => (a -> m b) -> URec Float a -> m (URec Float b) Source

sequence :: Monad m => URec Float (m a) -> m (URec Float a) Source

Traversable (URec Int :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec Int a -> f (URec Int b) Source

sequenceA :: Applicative f => URec Int (f a) -> f (URec Int a) Source

mapM :: Monad m => (a -> m b) -> URec Int a -> m (URec Int b) Source

sequence :: Monad m => URec Int (m a) -> m (URec Int a) Source

Traversable (URec Word :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec Word a -> f (URec Word b) Source

sequenceA :: Applicative f => URec Word (f a) -> f (URec Word a) Source

mapM :: Monad m => (a -> m b) -> URec Word a -> m (URec Word b) Source

sequence :: Monad m => URec Word (m a) -> m (URec Word a) Source

Traversable (URec (Ptr ()) :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> URec (Ptr ()) a -> f (URec (Ptr ()) b) Source

sequenceA :: Applicative f => URec (Ptr ()) (f a) -> f (URec (Ptr ()) a) Source

mapM :: Monad m => (a -> m b) -> URec (Ptr ()) a -> m (URec (Ptr ()) b) Source

sequence :: Monad m => URec (Ptr ()) (m a) -> m (URec (Ptr ()) a) Source

Traversable f => Traversable (Alt f)

Since: base-4.12.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Alt f a -> f0 (Alt f b) Source

sequenceA :: Applicative f0 => Alt f (f0 a) -> f0 (Alt f a) Source

mapM :: Monad m => (a -> m b) -> Alt f a -> m (Alt f b) Source

sequence :: Monad m => Alt f (m a) -> m (Alt f a) Source

Traversable f => Traversable (Ap f)

Since: base-4.12.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Ap f a -> f0 (Ap f b) Source

sequenceA :: Applicative f0 => Ap f (f0 a) -> f0 (Ap f a) Source

mapM :: Monad m => (a -> m b) -> Ap f a -> m (Ap f b) Source

sequence :: Monad m => Ap f (m a) -> m (Ap f a) Source

Traversable (Const m :: Type -> Type)

Since: base-4.7.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Const m a -> f (Const m b) Source

sequenceA :: Applicative f => Const m (f a) -> f (Const m a) Source

mapM :: Monad m0 => (a -> m0 b) -> Const m a -> m0 (Const m b) Source

sequence :: Monad m0 => Const m (m0 a) -> m0 (Const m a) Source

Traversable (K1 i c :: Type -> Type)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> K1 i c a -> f (K1 i c b) Source

sequenceA :: Applicative f => K1 i c (f a) -> f (K1 i c a) Source

mapM :: Monad m => (a -> m b) -> K1 i c a -> m (K1 i c b) Source

sequence :: Monad m => K1 i c (m a) -> m (K1 i c a) Source

(Traversable f, Traversable g) => Traversable (f :+: g)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> (f :+: g) a -> f0 ((f :+: g) b) Source

sequenceA :: Applicative f0 => (f :+: g) (f0 a) -> f0 ((f :+: g) a) Source

mapM :: Monad m => (a -> m b) -> (f :+: g) a -> m ((f :+: g) b) Source

sequence :: Monad m => (f :+: g) (m a) -> m ((f :+: g) a) Source

(Traversable f, Traversable g) => Traversable (f :*: g)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> (f :*: g) a -> f0 ((f :*: g) b) Source

sequenceA :: Applicative f0 => (f :*: g) (f0 a) -> f0 ((f :*: g) a) Source

mapM :: Monad m => (a -> m b) -> (f :*: g) a -> m ((f :*: g) b) Source

sequence :: Monad m => (f :*: g) (m a) -> m ((f :*: g) a) Source

(Traversable f, Traversable g) => Traversable (Sum f g)

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Sum

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Sum f g a -> f0 (Sum f g b) Source

sequenceA :: Applicative f0 => Sum f g (f0 a) -> f0 (Sum f g a) Source

mapM :: Monad m => (a -> m b) -> Sum f g a -> m (Sum f g b) Source

sequence :: Monad m => Sum f g (m a) -> m (Sum f g a) Source

(Traversable f, Traversable g) => Traversable (Product f g)

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Product

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Product f g a -> f0 (Product f g b) Source

sequenceA :: Applicative f0 => Product f g (f0 a) -> f0 (Product f g a) Source

mapM :: Monad m => (a -> m b) -> Product f g a -> m (Product f g b) Source

sequence :: Monad m => Product f g (m a) -> m (Product f g a) Source

Traversable f => Traversable (M1 i c f)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> M1 i c f a -> f0 (M1 i c f b) Source

sequenceA :: Applicative f0 => M1 i c f (f0 a) -> f0 (M1 i c f a) Source

mapM :: Monad m => (a -> m b) -> M1 i c f a -> m (M1 i c f b) Source

sequence :: Monad m => M1 i c f (m a) -> m (M1 i c f a) Source

(Traversable f, Traversable g) => Traversable (f :.: g)

Since: base-4.9.0.0

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f0 => (a -> f0 b) -> (f :.: g) a -> f0 ((f :.: g) b) Source

sequenceA :: Applicative f0 => (f :.: g) (f0 a) -> f0 ((f :.: g) a) Source

mapM :: Monad m => (a -> m b) -> (f :.: g) a -> m ((f :.: g) b) Source

sequence :: Monad m => (f :.: g) (m a) -> m ((f :.: g) a) Source

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

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Compose

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Compose f g a -> f0 (Compose f g b) Source

sequenceA :: Applicative f0 => Compose f g (f0 a) -> f0 (Compose f g a) Source

mapM :: Monad m => (a -> m b) -> Compose f g a -> m (Compose f g b) Source

sequence :: Monad m => Compose f g (m a) -> m (Compose f g a) Source

Utility functions

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b) Source

for is traverse with its arguments flipped. For a version that ignores the results see for_.

forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Source

forM is mapM with its arguments flipped. For a version that ignores the results see forM_.

mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Source

The mapAccumL function behaves like a combination of fmap and foldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.

mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Source

The mapAccumR function behaves like a combination of fmap and foldr; it applies a function to each element of a structure, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.

General definitions for superclass methods

fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b Source

This function may be used as a value for fmap in a Functor instance, provided that traverse is defined. (Using fmapDefault with a Traversable instance defined only by sequenceA will result in infinite recursion.)

fmapDefault f ≡ runIdentity . traverse (Identity . f)

foldMapDefault :: forall t m a. (Traversable t, Monoid m) => (a -> m) -> t a -> m Source

This function may be used as a value for foldMap in a Foldable instance.

foldMapDefault f ≡ getConst . traverse (Const . f)

© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/8.6.1/docs/html/libraries/base-4.12.0.0/Data-Traversable.html