{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeOperators #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  GHC.Internal.Data.Traversable
-- Copyright   :  Conor McBride and Ross Paterson 2005
-- License     :  BSD-style (see the LICENSE file in the distribution)
--
-- Maintainer  :  libraries@haskell.org
-- Stability   :  stable
-- Portability :  portable
--
-- Class of data structures that can be traversed from left to right,
-- performing an action on each element.  Instances are expected to satisfy
-- the listed [laws](#laws).
-----------------------------------------------------------------------------

module GHC.Internal.Data.Traversable (
    -- * The 'Traversable' class
    Traversable(..),
    -- * Utility functions
    for,
    forM,
    forAccumM,
    mapAccumL,
    mapAccumR,
    mapAccumM,
    -- * General definitions for superclass methods
    fmapDefault,
    foldMapDefault,
    ) where

import GHC.Internal.Data.Coerce
import GHC.Internal.Data.Either ( Either(..) )
import GHC.Internal.Data.Foldable
import GHC.Internal.Data.Functor
import GHC.Internal.Data.Functor.Const ( Const(..) )
import GHC.Internal.Data.Functor.Identity ( Identity(..) )
import GHC.Internal.Data.Functor.Utils ( StateL(..), StateR(..), StateT(..), (#.) )
import GHC.Internal.Data.Monoid ( Dual(..), Sum(..), Product(..),
                     First(..), Last(..), Alt(..), Ap(..) )
import GHC.Internal.Data.Ord ( Down(..) )
import GHC.Internal.Data.Proxy ( Proxy(..) )

import GHC.Internal.Arr
import GHC.Internal.Base ( Applicative(..), Monad(..), Monoid, Maybe(..), NonEmpty(..),
                  ($), (.), id, flip )
import GHC.Internal.Generics
import qualified GHC.Internal.List as List ( foldr )
import GHC.Tuple (Solo (..))

-- $setup
-- >>> import Prelude
-- >>> import GHC.Internal.Data.Maybe (catMaybes, mapMaybe)
-- >>> import GHC.Internal.Data.Either (rights)
-- >>> import GHC.Internal.Data.Foldable (traverse_)

-- XXX: Missing haddock feature.  Links to anchors in other modules
-- don't have a sensible way to name the link within the module itself.
-- Thus, the below "Data.Traversable#overview" works well when shown as
-- @Data.Traversable@ from other modules, but in the home module it should
-- be possible to specify alternative link text. :-(

-- | Functors representing data structures that can be transformed to
-- structures of the /same shape/ by performing an 'Applicative' (or,
-- therefore, 'Monad') action on each element from left to right.
--
-- A more detailed description of what /same shape/ means, the various methods,
-- how traversals are constructed, and example advanced use-cases can be found
-- in the __Overview__ section of "Data.Traversable#overview".
--
-- For the class laws see the __Laws__ section of "Data.Traversable#laws".
--
class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}

    -- | 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 'Data.Foldable.traverse_'.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- In the first two examples we show each evaluated action mapping to the
    -- output structure.
    --
    -- >>> traverse Just [1,2,3,4]
    -- Just [1,2,3,4]
    --
    -- >>> traverse id [Right 1, Right 2, Right 3, Right 4]
    -- Right [1,2,3,4]
    --
    -- In the next examples, we show that 'Nothing' and 'Left' values short
    -- circuit the created structure.
    --
    -- >>> traverse (const Nothing) [1,2,3,4]
    -- Nothing
    --
    -- >>> traverse (\x -> if odd x then Just x else Nothing)  [1,2,3,4]
    -- Nothing
    --
    -- >>> traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]
    -- Left 0
    --
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    {-# INLINE traverse #-}  -- See Note [Inline default methods]
    traverse a -> f b
f = t (f b) -> f (t b)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a)
sequenceA (t (f b) -> f (t b)) -> (t a -> t (f b)) -> t a -> f (t b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> t a -> t (f b)
forall a b. (a -> b) -> t a -> t b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> f b
f

    -- | Evaluate each action in the structure from left to right, and
    -- collect the results. For a version that ignores the results
    -- see 'Data.Foldable.sequenceA_'.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- For the first two examples we show sequenceA fully evaluating a
    -- a structure and collecting the results.
    --
    -- >>> sequenceA [Just 1, Just 2, Just 3]
    -- Just [1,2,3]
    --
    -- >>> sequenceA [Right 1, Right 2, Right 3]
    -- Right [1,2,3]
    --
    -- The next two example show 'Nothing' and 'Just' will short circuit
    -- the resulting structure if present in the input. For more context,
    -- check the 'Traversable' instances for 'Either' and 'Maybe'.
    --
    -- >>> sequenceA [Just 1, Just 2, Just 3, Nothing]
    -- Nothing
    --
    -- >>> sequenceA [Right 1, Right 2, Right 3, Left 4]
    -- Left 4
    --
    sequenceA :: Applicative f => t (f a) -> f (t a)
    {-# INLINE sequenceA #-}  -- See Note [Inline default methods]
    sequenceA = (f a -> f a) -> t (f a) -> f (t a)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b)
traverse f a -> f a
forall a. a -> a
id

    -- | 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 'Data.Foldable.mapM_'.
    --
    -- ==== __Examples__
    --
    -- 'mapM' is literally a 'traverse' with a type signature restricted
    -- to 'Monad'. Its implementation may be more efficient due to additional
    -- power of 'Monad'.
    --
    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    {-# INLINE mapM #-}  -- See Note [Inline default methods]
    mapM = (a -> m b) -> t a -> m (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b)
traverse

    -- | Evaluate each monadic action in the structure from left to
    -- right, and collect the results. For a version that ignores the
    -- results see 'Data.Foldable.sequence_'.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- The first two examples are instances where the input and
    -- and output of 'sequence' are isomorphic.
    --
    -- >>> sequence $ Right [1,2,3,4]
    -- [Right 1,Right 2,Right 3,Right 4]
    --
    -- >>> sequence $ [Right 1,Right 2,Right 3,Right 4]
    -- Right [1,2,3,4]
    --
    -- The following examples demonstrate short circuit behavior
    -- for 'sequence'.
    --
    -- >>> sequence $ Left [1,2,3,4]
    -- Left [1,2,3,4]
    --
    -- >>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
    -- Left 0
    --
    sequence :: Monad m => t (m a) -> m (t a)
    {-# INLINE sequence #-}  -- See Note [Inline default methods]
    sequence = t (m a) -> m (t a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a)
sequenceA

{- Note [Inline default methods]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider

   class ... => Traversable t where
       ...
       mapM :: Monad m => (a -> m b) -> t a -> m (t b)
       mapM = traverse   -- Default method

   instance Traversable [] where
       {-# INLINE traverse #-}
       traverse = ...code for traverse on lists ...

This gives rise to a list-instance of mapM looking like this

  $fTraversable[]_$ctraverse = ...code for traverse on lists...
       {-# INLINE $fTraversable[]_$ctraverse #-}
  $fTraversable[]_$cmapM    = $fTraversable[]_$ctraverse

Now the $ctraverse obediently inlines into the RHS of $cmapM, /but/
that's all!  We get

  $fTraversable[]_$cmapM = ...code for traverse on lists...

with NO INLINE pragma!  This happens even though 'traverse' had an
INLINE pragma because the author knew it should be inlined pretty
vigorously.

Indeed, it turned out that the rhs of $cmapM was just too big to
inline, so all uses of mapM on lists used a terribly inefficient
dictionary-passing style, because of its 'Monad m =>' type.  Disaster!

Solution: add an INLINE pragma on the default method:

   class ... => Traversable t where
       ...
       mapM :: Monad m => (a -> m b) -> t a -> m (t b)
       {-# INLINE mapM #-}     -- VERY IMPORTANT!
       mapM = traverse
-}

-- instances for Prelude types

-- | @since base-2.01
instance Traversable Maybe where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse a -> f b
_ Maybe a
Nothing = Maybe b -> f (Maybe b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe b
forall a. Maybe a
Nothing
    traverse a -> f b
f (Just a
x) = b -> Maybe b
forall a. a -> Maybe a
Just (b -> Maybe b) -> f b -> f (Maybe b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x

-- | @since base-2.01
instance Traversable [] where
    {-# INLINE traverse #-} -- so that traverse can fuse
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse a -> f b
f = (a -> f [b] -> f [b]) -> f [b] -> [a] -> f [b]
forall a b. (a -> b -> b) -> b -> [a] -> b
List.foldr a -> f [b] -> f [b]
cons_f ([b] -> f [b]
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure [])
      where cons_f :: a -> f [b] -> f [b]
cons_f a
x f [b]
ys = (b -> [b] -> [b]) -> f b -> f [b] -> f [b]
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (:) (a -> f b
f a
x) f [b]
ys

-- | @since base-4.9.0.0
instance Traversable NonEmpty where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NonEmpty a -> f (NonEmpty b)
traverse a -> f b
f ~(a
a :| [a]
as) = (b -> [b] -> NonEmpty b) -> f b -> f [b] -> f (NonEmpty b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
(:|) (a -> f b
f a
a) ((a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse a -> f b
f [a]
as)

-- | @since base-4.7.0.0
instance Traversable (Either a) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Either a a -> f (Either a b)
traverse a -> f b
_ (Left a
x) = Either a b -> f (Either a b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Either a b
forall a b. a -> Either a b
Left a
x)
    traverse a -> f b
f (Right a
y) = b -> Either a b
forall a b. b -> Either a b
Right (b -> Either a b) -> f b -> f (Either a b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
y

-- | @since base-4.15
deriving instance Traversable Solo

-- | @since base-4.7.0.0
instance Traversable ((,) a) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> (a, a) -> f (a, b)
traverse a -> f b
f (a
x, a
y) = (,) a
x (b -> (a, b)) -> f b -> f (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
y

-- | @since base-2.01
instance Ix i => Traversable (Array i) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array i a -> f (Array i b)
traverse a -> f b
f Array i a
arr = (i, i) -> [b] -> Array i b
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Array i a -> (i, i)
forall i e. Array i e -> (i, i)
bounds Array i a
arr) ([b] -> Array i b) -> f [b] -> f (Array i b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse a -> f b
f (Array i a -> [a]
forall i e. Array i e -> [e]
elems Array i a
arr)

-- | @since base-4.7.0.0
instance Traversable Proxy where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Proxy a -> f (Proxy b)
traverse a -> f b
_ Proxy a
_ = Proxy b -> f (Proxy b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy b
forall {k} (t :: k). Proxy t
Proxy
    {-# INLINE traverse #-}
    sequenceA :: forall (f :: * -> *) a. Applicative f => Proxy (f a) -> f (Proxy a)
sequenceA Proxy (f a)
_ = Proxy a -> f (Proxy a)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy a
forall {k} (t :: k). Proxy t
Proxy
    {-# INLINE sequenceA #-}
    mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Proxy a -> m (Proxy b)
mapM a -> m b
_ Proxy a
_ = Proxy b -> m (Proxy b)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy b
forall {k} (t :: k). Proxy t
Proxy
    {-# INLINE mapM #-}
    sequence :: forall (m :: * -> *) a. Monad m => Proxy (m a) -> m (Proxy a)
sequence Proxy (m a)
_ = Proxy a -> m (Proxy a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy a
forall {k} (t :: k). Proxy t
Proxy
    {-# INLINE sequence #-}

-- | @since base-4.7.0.0
instance Traversable (Const m) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Const m a -> f (Const m b)
traverse a -> f b
_ (Const m
m) = Const m b -> f (Const m b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Const m b -> f (Const m b)) -> Const m b -> f (Const m b)
forall a b. (a -> b) -> a -> b
$ m -> Const m b
forall {k} a (b :: k). a -> Const a b
Const m
m

-- | @since base-4.8.0.0
instance Traversable Dual where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Dual a -> f (Dual b)
traverse a -> f b
f (Dual a
x) = b -> Dual b
forall a. a -> Dual a
Dual (b -> Dual b) -> f b -> f (Dual b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x

-- | @since base-4.8.0.0
instance Traversable Sum where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Sum a -> f (Sum b)
traverse a -> f b
f (Sum a
x) = b -> Sum b
forall a. a -> Sum a
Sum (b -> Sum b) -> f b -> f (Sum b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x

-- | @since base-4.8.0.0
instance Traversable Product where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Product a -> f (Product b)
traverse a -> f b
f (Product a
x) = b -> Product b
forall a. a -> Product a
Product (b -> Product b) -> f b -> f (Product b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x

-- | @since base-4.8.0.0
instance Traversable First where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> First a -> f (First b)
traverse a -> f b
f (First Maybe a
x) = Maybe b -> First b
forall a. Maybe a -> First a
First (Maybe b -> First b) -> f (Maybe b) -> f (First b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse a -> f b
f Maybe a
x

-- | @since base-4.8.0.0
instance Traversable Last where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Last a -> f (Last b)
traverse a -> f b
f (Last Maybe a
x) = Maybe b -> Last b
forall a. Maybe a -> Last a
Last (Maybe b -> Last b) -> f (Maybe b) -> f (Last b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse a -> f b
f Maybe a
x

-- | @since base-4.12.0.0
instance (Traversable f) => Traversable (Alt f) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Alt f a -> f (Alt f b)
traverse a -> f b
f (Alt f a
x) = f b -> Alt f b
forall {k} (f :: k -> *) (a :: k). f a -> Alt f a
Alt (f b -> Alt f b) -> f (f b) -> f (Alt f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> f a -> f (f b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> f a -> f (f b)
traverse a -> f b
f f a
x

-- | @since base-4.12.0.0
instance (Traversable f) => Traversable (Ap f) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Ap f a -> f (Ap f b)
traverse a -> f b
f (Ap f a
x) = f b -> Ap f b
forall {k} (f :: k -> *) (a :: k). f a -> Ap f a
Ap (f b -> Ap f b) -> f (f b) -> f (Ap f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> f a -> f (f b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> f a -> f (f b)
traverse a -> f b
f f a
x

-- | @since base-4.9.0.0
deriving instance Traversable Identity


-- Instances for GHC.Generics
-- | @since base-4.9.0.0
instance Traversable U1 where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> U1 a -> f (U1 b)
traverse a -> f b
_ U1 a
_ = U1 b -> f (U1 b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 b
forall k (p :: k). U1 p
U1
    {-# INLINE traverse #-}
    sequenceA :: forall (f :: * -> *) a. Applicative f => U1 (f a) -> f (U1 a)
sequenceA U1 (f a)
_ = U1 a -> f (U1 a)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 a
forall k (p :: k). U1 p
U1
    {-# INLINE sequenceA #-}
    mapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> U1 a -> m (U1 b)
mapM a -> m b
_ U1 a
_ = U1 b -> m (U1 b)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 b
forall k (p :: k). U1 p
U1
    {-# INLINE mapM #-}
    sequence :: forall (m :: * -> *) a. Monad m => U1 (m a) -> m (U1 a)
sequence U1 (m a)
_ = U1 a -> m (U1 a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 a
forall k (p :: k). U1 p
U1
    {-# INLINE sequence #-}

-- | @since base-4.9.0.0
deriving instance Traversable V1

-- | @since base-4.9.0.0
deriving instance Traversable Par1

-- | @since base-4.9.0.0
deriving instance Traversable f => Traversable (Rec1 f)

-- | @since base-4.9.0.0
deriving instance Traversable (K1 i c)

-- | @since base-4.9.0.0
deriving instance Traversable f => Traversable (M1 i c f)

-- | @since base-4.9.0.0
deriving instance (Traversable f, Traversable g) => Traversable (f :+: g)

-- | @since base-4.9.0.0
deriving instance (Traversable f, Traversable g) => Traversable (f :*: g)

-- | @since base-4.9.0.0
deriving instance (Traversable f, Traversable g) => Traversable (f :.: g)

-- | @since base-4.9.0.0
deriving instance Traversable UAddr

-- | @since base-4.9.0.0
deriving instance Traversable UChar

-- | @since base-4.9.0.0
deriving instance Traversable UDouble

-- | @since base-4.9.0.0
deriving instance Traversable UFloat

-- | @since base-4.9.0.0
deriving instance Traversable UInt

-- | @since base-4.9.0.0
deriving instance Traversable UWord

-- Instance for Data.Ord
-- | @since base-4.12.0.0
deriving instance Traversable Down

-- general functions

-- | 'for' is 'traverse' with its arguments flipped. For a version
-- that ignores the results see 'Data.Foldable.for_'.
for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
{-# INLINE for #-}
for :: forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
t a -> (a -> f b) -> f (t b)
for = ((a -> f b) -> t a -> f (t b)) -> t a -> (a -> f b) -> f (t b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b)
traverse

-- | 'forM' is 'mapM' with its arguments flipped. For a version that
-- ignores the results see 'Data.Foldable.forM_'.
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
{-# INLINE forM #-}
forM :: forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM = ((a -> m b) -> t a -> m (t b)) -> t a -> (a -> m b) -> m (t b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> m b) -> t a -> m (t b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)
mapM

-- |The 'mapAccumL' function behaves like a combination of 'fmap'
-- and 'Data.Foldable.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.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> mapAccumL (\a b -> (a + b, a)) 0 [1..10]
-- (55,[0,1,3,6,10,15,21,28,36,45])
--
-- >>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]
-- ("012345",["0","01","012","0123","01234"])
--
mapAccumL :: forall t s a b. Traversable t
          => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
-- See Note [Function coercion] in Data.Functor.Utils.
mapAccumL :: forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL s -> a -> (s, b)
f s
s t a
t = ((a -> StateL s b) -> t a -> StateL s (t b))
-> (a -> s -> (s, b)) -> t a -> s -> (s, t b)
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse @t @(StateL s) @a @b) ((s -> a -> (s, b)) -> a -> s -> (s, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> a -> (s, b)
f) t a
t s
s

-- |The 'mapAccumR' function behaves like a combination of 'fmap'
-- and 'Data.Foldable.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.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> mapAccumR (\a b -> (a + b, a)) 0 [1..10]
-- (55,[54,52,49,45,40,34,27,19,10,0])
--
-- >>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]
-- ("054321",["05432","0543","054","05","0"])
--
mapAccumR :: forall t s a b. Traversable t
          => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
-- See Note [Function coercion] in Data.Functor.Utils.
mapAccumR :: forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR s -> a -> (s, b)
f s
s t a
t = ((a -> StateR s b) -> t a -> StateR s (t b))
-> (a -> s -> (s, b)) -> t a -> s -> (s, t b)
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse @t @(StateR s) @a @b) ((s -> a -> (s, b)) -> a -> s -> (s, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> a -> (s, b)
f) t a
t s
s

-- | The `mapAccumM` function behaves like a combination of `mapM` and
-- `mapAccumL` that traverses the structure while evaluating the actions
-- and passing an accumulating parameter from left to right.
-- It returns a final value of this accumulator together with the new structure.
-- The accumulator is often used for caching the intermediate results of a computation.
--
--  @since base-4.18.0.0
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> let expensiveDouble a = putStrLn ("Doubling " <> show a) >> pure (2 * a)
-- >>> :{
-- mapAccumM (\cache a -> case lookup a cache of
--     Nothing -> expensiveDouble a >>= \double -> pure ((a, double):cache, double)
--     Just double -> pure (cache, double)
--     ) [] [1, 2, 3, 1, 2, 3]
-- :}
-- Doubling 1
-- Doubling 2
-- Doubling 3
-- ([(3,6),(2,4),(1,2)],[2,4,6,2,4,6])
--
mapAccumM
  :: forall m t s a b. (Monad m, Traversable t)
  => (s -> a -> m (s, b))
  -> s -> t a -> m (s, t b)
mapAccumM :: forall (m :: * -> *) (t :: * -> *) s a b.
(Monad m, Traversable t) =>
(s -> a -> m (s, b)) -> s -> t a -> m (s, t b)
mapAccumM s -> a -> m (s, b)
f s
s t a
t = ((a -> StateT s m b) -> t a -> StateT s m (t b))
-> (a -> StateT s m b) -> t a -> s -> m (s, t b)
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM @t @(StateT s m) @a @b) ((s -> m (s, b)) -> StateT s m b
forall s (m :: * -> *) a. (s -> m (s, a)) -> StateT s m a
StateT ((s -> m (s, b)) -> StateT s m b)
-> (a -> s -> m (s, b)) -> a -> StateT s m b
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (s -> a -> m (s, b)) -> a -> s -> m (s, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> a -> m (s, b)
f) t a
t s
s

-- | 'forAccumM' is 'mapAccumM' with the arguments rearranged.
--
-- @since base-4.18.0.0
forAccumM
  :: (Monad m, Traversable t)
  => s -> t a -> (s -> a -> m (s, b)) -> m (s, t b)
{-# INLINE forAccumM #-}
forAccumM :: forall (m :: * -> *) (t :: * -> *) s a b.
(Monad m, Traversable t) =>
s -> t a -> (s -> a -> m (s, b)) -> m (s, t b)
forAccumM s
s t a
t s -> a -> m (s, b)
f = (s -> a -> m (s, b)) -> s -> t a -> m (s, t b)
forall (m :: * -> *) (t :: * -> *) s a b.
(Monad m, Traversable t) =>
(s -> a -> m (s, b)) -> s -> t a -> m (s, t b)
mapAccumM s -> a -> m (s, b)
f s
s t a
t

-- | 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)
-- @
fmapDefault :: forall t a b . Traversable t
            => (a -> b) -> t a -> t b
{-# INLINE fmapDefault #-}
-- See Note [Function coercion] in Data.Functor.Utils.
fmapDefault :: forall (t :: * -> *) a b. Traversable t => (a -> b) -> t a -> t b
fmapDefault = ((a -> Identity b) -> t a -> Identity (t b))
-> (a -> b) -> t a -> t b
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse @t @Identity @a @b)

-- | This function may be used as a value for `Data.Foldable.foldMap`
-- in a `Foldable` instance.
--
-- @
-- 'foldMapDefault' f ≡ 'getConst' . 'traverse' ('Const' . f)
-- @
foldMapDefault :: forall t m a . (Traversable t, Monoid m)
               => (a -> m) -> t a -> m
{-# INLINE foldMapDefault #-}
-- See Note [Function coercion] in Data.Functor.Utils.
foldMapDefault :: forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault = ((a -> Const m ()) -> t a -> Const m (t ()))
-> (a -> m) -> t a -> m
forall a b. Coercible a b => a -> b
coerce (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse @t @(Const m) @a @())