{-# LANGUAGE Safe #-}

-- |
-- Module      :  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 Data.Traversable (
    -- * The 'Traversable' class
    Traversable(..),
    -- * Utility functions
    for,
    forM,
    forAccumM,
    mapAccumL,
    mapAccumR,
    mapAccumM,
    -- * General definitions for superclass methods
    fmapDefault,
    foldMapDefault,

    -- * Overview
    -- $overview

    -- ** The 'traverse' and 'mapM' methods
    -- $traverse

    -- *** Their 'Foldable', just the effects, analogues.
    -- $effectful

    -- *** Result multiplicity
    -- $multiplicity

    -- ** The 'sequenceA' and 'sequence' methods
    -- $sequence

    -- *** Care with default method implementations
    -- $seqdefault

    -- *** Monadic short circuits
    -- $seqshort

    -- ** Example binary tree instance
    -- $tree_instance

    -- *** Pre-order and post-order tree traversal
    -- $tree_order

    -- ** Making construction intuitive
    --
    -- $construction

    -- * Advanced traversals
    -- $advanced

    -- *** Coercion
    -- $coercion

    -- ** Identity: the 'fmapDefault' function
    -- $identity

    -- ** State: the 'mapAccumL', 'mapAccumR' functions
    -- $stateful

    -- ** Const: the 'foldMapDefault' function
    -- $phantom

    -- ** ZipList: transposing lists of lists
    -- $ziplist

    -- * Laws
    --
    -- $laws

    -- * See also
    -- $also
    ) where

import GHC.Internal.Data.Traversable

-- $overview
--
-- #overview#
-- Traversable structures support element-wise sequencing of 'Applicative'
-- effects (thus also 'Monad' effects) to construct new structures of
-- __the same shape__ as the input.
--
-- To illustrate what is meant by /same shape/, if the input structure is
-- __@[a]@__, each output structure is a list __@[b]@__ of the same length as
-- the input.  If the input is a __@Tree a@__, each output __@Tree b@__ has the
-- same graph of intermediate nodes and leaves.  Similarly, if the input is a
-- 2-tuple __@(x, a)@__, each output is a 2-tuple __@(x, b)@__, and so forth.
--
-- It is in fact possible to decompose a traversable structure __@t a@__ into
-- its shape (a.k.a. /spine/) of type __@t ()@__ and its element list
-- __@[a]@__.  The original structure can be faithfully reconstructed from its
-- spine and element list.
--
-- The implementation of a @Traversable@ instance for a given structure follows
-- naturally from its type; see the [Construction](#construction) section for
-- details.
-- Instances must satisfy the laws listed in the [Laws section](#laws).
-- The diverse uses of @Traversable@ structures result from the many possible
-- choices of Applicative effects.
-- See the [Advanced Traversals](#advanced) section for some examples.
--
-- Every @Traversable@ structure is both a 'Functor' and 'Foldable' because it
-- is possible to implement the requisite instances in terms of 'traverse' by
-- using 'fmapDefault' for 'fmap' and 'foldMapDefault' for 'foldMap'.  Direct
-- fine-tuned implementations of these superclass methods can in some cases be
-- more efficient.

------------------

-- $traverse
-- For an 'Applicative' functor __@f@__ and a @Traversable@ functor __@t@__,
-- the type signatures of 'traverse' and 'fmap' are rather similar:
--
-- > fmap     :: (a -> f b) -> t a -> t (f b)
-- > traverse :: (a -> f b) -> t a -> f (t b)
--
-- The key difference is that 'fmap' produces a structure whose elements (of
-- type __@f b@__) are individual effects, while 'traverse' produces an
-- aggregate effect yielding structures of type __@t b@__.
--
-- For example, when __@f@__ is the __@IO@__ monad, and __@t@__ is __@List@__,
-- 'fmap' yields a list of IO actions, whereas 'traverse' constructs an IO
-- action that evaluates to a list of the return values of the individual
-- actions performed left-to-right.
--
-- > traverse :: (a -> IO b) -> [a] -> IO [b]
--
-- The 'mapM' function is a specialisation of 'traverse' to the case when
-- __@f@__ is a 'Monad'.  For monads, 'mapM' is more idiomatic than 'traverse'.
-- The two are otherwise generally identical (though 'mapM' may be specifically
-- optimised for monads, and could be more efficient than using the more
-- general 'traverse').
--
-- > traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
-- > mapM     :: (Monad       m, Traversable t) => (a -> m b) -> t a -> m (t b)
--
-- When the traversable term is a simple variable or expression, and the
-- monadic action to run is a non-trivial do block, it can be more natural to
-- write the action last.  This idiom is supported by 'for', 'forM', and
-- 'forAccumM' which are the flipped versions of 'traverse', 'mapM', and
-- 'mapAccumM' respectively.

------------------

-- $multiplicity
--
-- #multiplicity#
-- When 'traverse' or 'mapM' is applied to an empty structure __@ts@__ (one for
-- which __@'null' ts@__ is 'True') the return value is __@pure ts@__
-- regardless of the provided function __@g :: a -> f b@__.  It is not possible
-- to apply the function when no values of type __@a@__ are available, but its
-- type determines the relevant instance of 'pure'.
--
-- prop> null ts ==> traverse g ts == pure ts
--
-- Otherwise, when __@ts@__ is non-empty and at least one value of type __@b@__
-- results from each __@f a@__, the structures __@t b@__ have /the same shape/
-- (list length, graph of tree nodes, ...) as the input structure __@t a@__,
-- but the slots previously occupied by elements of type __@a@__ now hold
-- elements of type __@b@__.
--
-- A single traversal may produce one, zero or many such structures.  The zero
-- case happens when one of the effects __@f a@__ sequenced as part of the
-- traversal yields no replacement values.  Otherwise, the many case happens
-- when one of sequenced effects yields multiple values.
--
-- The 'traverse' function does not perform selective filtering of slots in the
-- output structure as with e.g. 'Data.Maybe.mapMaybe'.
--
-- >>> let incOdd n = if odd n then Just $ n + 1 else Nothing
-- >>> mapMaybe incOdd [1, 2, 3]
-- [2,4]
-- >>> traverse incOdd [1, 3, 5]
-- Just [2,4,6]
-- >>> traverse incOdd [1, 2, 3]
-- Nothing
--
-- In the above examples, with 'Maybe' as the 'Applicative' __@f@__, we see
-- that the number of __@t b@__ structures produced by 'traverse' may differ
-- from one: it is zero when the result short-circuits to __@Nothing@__.  The
-- same can happen when __@f@__ is __@List@__ and the result is __@[]@__, or
-- __@f@__ is __@Either e@__ and the result is __@Left (x :: e)@__, or perhaps
-- the 'Control.Applicative.empty' value of some
-- 'Control.Applicative.Alternative' functor.
--
-- When __@f@__ is e.g. __@List@__, and the map __@g :: a -> [b]@__ returns
-- more than one value for some inputs __@a@__ (and at least one for all
-- __@a@__), the result of __@mapM g ts@__ will contain multiple structures of
-- the same shape as __@ts@__:
--
-- prop> length (mapM g ts) == product (fmap (length . g) ts)
--
-- For example:
--
-- >>> length $ mapM (\n -> [1..n]) [1..6]
-- 720
-- >>> product $ length . (\n -> [1..n]) <$> [1..6]
-- 720
--
-- In other words, a traversal with a function __@g :: a -> [b]@__, over an
-- input structure __@t a@__, yields a list __@[t b]@__, whose length is the
-- product of the lengths of the lists that @g@ returns for each element of the
-- input structure!  The individual elements __@a@__ of the structure are
-- replaced by each element of __@g a@__ in turn:
--
-- >>> mapM (\n -> [1..n]) $ Just 3
-- [Just 1,Just 2,Just 3]
-- >>> mapM (\n -> [1..n]) [1..3]
-- [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3]]
--
-- If any element of the structure __@t a@__ is mapped by @g@ to an empty list,
-- then the entire aggregate result is empty, because no value is available to
-- fill one of the slots of the output structure:
--
-- >>> mapM (\n -> [1..n]) $ [0..6] -- [1..0] is empty
-- []

------------------

-- $effectful
-- #effectful#
--
-- The 'traverse' and 'mapM' methods have analogues in the "Data.Foldable"
-- module.  These are 'traverse_' and 'mapM_', and their flipped variants
-- 'for_' and 'forM_', respectively.  The result type is __@f ()@__, they don't
-- return an updated structure, and can be used to sequence effects over all
-- the elements of a @Traversable@ (any 'Foldable') structure just for their
-- side-effects.
--
-- If the @Traversable@ structure is empty, the result is __@pure ()@__.  When
-- effects short-circuit, the __@f ()@__ result may, for example, be 'Nothing'
-- if __@f@__ is 'Maybe', or __@'Left' e@__ when it is __@'Either' e@__.
--
-- It is perhaps worth noting that 'Maybe' is not only a potential
-- 'Applicative' functor for the return value of the first argument of
-- 'traverse', but is also itself a 'Traversable' structure with either zero or
-- one element.  A convenient idiom for conditionally executing an action just
-- for its effects on a 'Just' value, and doing nothing otherwise is:
--
-- > -- action :: Monad m => a -> m ()
-- > -- mvalue :: Maybe a
-- > mapM_ action mvalue -- :: m ()
--
-- which is more concise than:
--
-- > maybe (return ()) action mvalue
--
-- The 'mapM_' idiom works verbatim if the type of __@mvalue@__ is later
-- refactored from __@Maybe a@__ to __@Either e a@__ (assuming it remains OK to
-- silently do nothing in the 'Left' case).

------------------

-- $sequence
--
-- #sequence#
-- The 'sequenceA' and 'sequence' methods are useful when what you have is a
-- container of pending applicative or monadic effects, and you want to combine
-- them into a single effect that produces zero or more containers with the
-- computed values.
--
-- > sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
-- > sequence  :: (Monad       m, Traversable t) => t (m a) -> m (t a)
-- > sequenceA = traverse id -- default definition
-- > sequence  = sequenceA   -- default definition
--
-- When the monad __@m@__ is 'System.IO.IO', applying 'sequence' to a list of
-- IO actions, performs each in turn, returning a list of the results:
--
-- > sequence [putStr "Hello ", putStrLn "World!"]
-- >     = (\a b -> [a,b]) <$> putStr "Hello " <*> putStrLn "World!"
-- >     = do u1 <- putStr "Hello "
-- >          u2 <- putStrLn "World!"
-- >          return [u1, u2]         -- In this case  [(), ()]
--
-- For 'sequenceA', the /non-deterministic/ behaviour of @List@ is most easily
-- seen in the case of a list of lists (of elements of some common fixed type).
-- The result is a cross-product of all the sublists:
--
-- >>> sequenceA [[0, 1, 2], [30, 40], [500]]
-- [[0,30,500],[0,40,500],[1,30,500],[1,40,500],[2,30,500],[2,40,500]]
--
-- Because the input list has three (sublist) elements, the result is a list of
-- triples (/same shape/).

------------------

-- $seqshort
--
-- #seqshort#
-- When the monad __@m@__ is 'Either' or 'Maybe' (more generally any
-- 'Control.Monad.MonadPlus'), the effect in question is to short-circuit the
-- result on encountering 'Left' or 'Nothing' (more generally
-- 'Control.Monad.mzero').
--
-- >>> sequence [Just 1,Just 2,Just 3]
-- Just [1,2,3]
-- >>> sequence [Just 1,Nothing,Just 3]
-- Nothing
-- >>> sequence [Right 1,Right 2,Right 3]
-- Right [1,2,3]
-- >>> sequence [Right 1,Left "sorry",Right 3]
-- Left "sorry"
--
-- The result of 'sequence' is all-or-nothing, either structures of exactly the
-- same shape as the input or none at all.  The 'sequence' function does not
-- perform selective filtering as with e.g. 'Data.Maybe.catMaybes' or
-- 'Data.Either.rights':
--
-- >>> catMaybes [Just 1,Nothing,Just 3]
-- [1,3]
-- >>> rights [Right 1,Left "sorry",Right 3]
-- [1,3]

------------------

-- $seqdefault
--
-- #seqdefault#
-- The 'traverse' method has a default implementation in terms of 'sequenceA':
--
-- > traverse g = sequenceA . fmap g
--
-- but relying on this default implementation is not recommended, it requires
-- that the structure is already independently a 'Functor'.  The definition of
-- 'sequenceA' in terms of __@traverse id@__ is much simpler than 'traverse'
-- expressed via a composition of 'sequenceA' and 'fmap'.  Instances should
-- generally implement 'traverse' explicitly.  It may in some cases also make
-- sense to implement a specialised 'mapM'.
--
-- Because 'fmapDefault' is defined in terms of 'traverse' (whose default
-- definition in terms of 'sequenceA' uses 'fmap'), you must not use
-- 'fmapDefault' to define the @Functor@ instance if the @Traversable@ instance
-- directly defines only 'sequenceA'.

------------------

-- $tree_instance
--
-- #tree#
-- The definition of a 'Traversable' instance for a binary tree is rather
-- similar to the corresponding instance of 'Functor', given the data type:
--
-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
-- a canonical @Functor@ instance would be
--
-- > instance Functor Tree where
-- >    fmap g Empty        = Empty
-- >    fmap g (Leaf x)     = Leaf (g x)
-- >    fmap g (Node l k r) = Node (fmap g l) (g k) (fmap g r)
--
-- a canonical @Traversable@ instance would be
--
-- > instance Traversable Tree where
-- >    traverse g Empty        = pure Empty
-- >    traverse g (Leaf x)     = Leaf <$> g x
-- >    traverse g (Node l k r) = Node <$> traverse g l <*> g k <*> traverse g r
--
-- This definition works for any __@g :: a -> f b@__, with __@f@__ an
-- Applicative functor, as the laws for @('<*>')@ imply the requisite
-- associativity.
--
-- We can add an explicit non-default 'mapM' if desired:
--
-- >    mapM g Empty        = return Empty
-- >    mapM g (Leaf x)     = Leaf <$> g x
-- >    mapM g (Node l k r) = do
-- >        ml <- mapM g l
-- >        mk <- g k
-- >        mr <- mapM g r
-- >        return $ Node ml mk mr
--
-- See [Construction](#construction) below for a more detailed exploration of
-- the general case, but as mentioned in [Overview](#overview) above, instance
-- definitions are typically rather simple, all the interesting behaviour is a
-- result of an interesting choice of 'Applicative' functor for a traversal.

-- $tree_order
--
-- It is perhaps worth noting that the traversal defined above gives an
-- /in-order/ sequencing of the elements.  If instead you want either
-- /pre-order/ (parent first, then child nodes) or post-order (child nodes
-- first, then parent) sequencing, you can define the instance accordingly:
--
-- > inOrderNode :: Tree a -> a -> Tree a -> Tree a
-- > inOrderNode l x r = Node l x r
-- >
-- > preOrderNode :: a -> Tree a -> Tree a -> Tree a
-- > preOrderNode x l r = Node l x r
-- >
-- > postOrderNode :: Tree a -> Tree a -> a -> Tree a
-- > postOrderNode l r x = Node l x r
-- >
-- > -- Traversable instance with in-order traversal
-- > instance Traversable Tree where
-- >     traverse g t = case t of
-- >         Empty      -> pure Empty
-- >         Leaf x     -> Leaf <$> g x
-- >         Node l x r -> inOrderNode <$> traverse g l <*> g x <*> traverse g r
-- >
-- > -- Traversable instance with pre-order traversal
-- > instance Traversable Tree where
-- >     traverse g t = case t of
-- >         Empty      -> pure Empty
-- >         Leaf x     -> Leaf <$> g x
-- >         Node l x r -> preOrderNode <$> g x <*> traverse g l <*> traverse g r
-- >
-- > -- Traversable instance with post-order traversal
-- > instance Traversable Tree where
-- >     traverse g t = case t of
-- >         Empty      -> pure Empty
-- >         Leaf x     -> Leaf <$> g x
-- >         Node l x r -> postOrderNode <$> traverse g l <*> traverse g r <*> g x
--
-- Since the same underlying Tree structure is used in all three cases, it is
-- possible to use @newtype@ wrappers to make all three available at the same
-- time!  The user need only wrap the root of the tree in the appropriate
-- @newtype@ for the desired traversal order.  Tne associated instance
-- definitions are shown below (see [coercion](#coercion) if unfamiliar with
-- the use of 'coerce' in the sample code):
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- >
-- > -- Default in-order traversal
-- >
-- > import Data.Coerce (coerce)
-- > import Data.Traversable
-- >
-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
-- > instance Functor  Tree where fmap    = fmapDefault
-- > instance Foldable Tree where foldMap = foldMapDefault
-- >
-- > instance Traversable Tree where
-- >     traverse _ Empty = pure Empty
-- >     traverse g (Leaf a) = Leaf <$> g a
-- >     traverse g (Node l a r) = Node <$> traverse g l <*> g a <*> traverse g r
-- >
-- > -- Optional pre-order traversal
-- >
-- > newtype PreOrderTree a = PreOrderTree (Tree a)
-- > instance Functor  PreOrderTree where fmap    = fmapDefault
-- > instance Foldable PreOrderTree where foldMap = foldMapDefault
-- >
-- > instance Traversable PreOrderTree where
-- >     traverse _ (PreOrderTree Empty)        = pure $ preOrderEmpty
-- >     traverse g (PreOrderTree (Leaf x))     = preOrderLeaf <$> g x
-- >     traverse g (PreOrderTree (Node l x r)) = preOrderNode
-- >         <$> g x
-- >         <*> traverse g (coerce l)
-- >         <*> traverse g (coerce r)
-- >
-- > preOrderEmpty :: forall a. PreOrderTree a
-- > preOrderEmpty = coerce (Empty @a)
-- > preOrderLeaf :: forall a. a -> PreOrderTree a
-- > preOrderLeaf = coerce (Leaf @a)
-- > preOrderNode :: a -> PreOrderTree a -> PreOrderTree a -> PreOrderTree a
-- > preOrderNode x l r = coerce (Node (coerce l) x (coerce r))
-- >
-- > -- Optional post-order traversal
-- >
-- > newtype PostOrderTree a = PostOrderTree (Tree a)
-- > instance Functor  PostOrderTree where fmap    = fmapDefault
-- > instance Foldable PostOrderTree where foldMap = foldMapDefault
-- >
-- > instance Traversable PostOrderTree where
-- >     traverse _ (PostOrderTree Empty)        = pure postOrderEmpty
-- >     traverse g (PostOrderTree (Leaf x))     = postOrderLeaf <$> g x
-- >     traverse g (PostOrderTree (Node l x r)) = postOrderNode
-- >         <$> traverse g (coerce l)
-- >         <*> traverse g (coerce r)
-- >         <*> g x
-- >
-- > postOrderEmpty :: forall a. PostOrderTree a
-- > postOrderEmpty = coerce (Empty @a)
-- > postOrderLeaf :: forall a. a -> PostOrderTree a
-- > postOrderLeaf = coerce (Leaf @a)
-- > postOrderNode :: PostOrderTree a -> PostOrderTree a -> a -> PostOrderTree a
-- > postOrderNode l r x = coerce (Node (coerce l) x (coerce r))
--
-- With the above, given a sample tree:
--
-- > inOrder :: Tree Int
-- > inOrder = Node (Node (Leaf 10) 3 (Leaf 20)) 5 (Leaf 42)
--
-- we have:
--
-- > import Data.Foldable (toList)
-- > print $ toList inOrder
-- > [10,3,20,5,42]
-- >
-- > print $ toList (coerce inOrder :: PreOrderTree Int)
-- > [5,3,10,20,42]
-- >
-- > print $ toList (coerce inOrder :: PostOrderTree Int)
-- > [10,20,3,42,5]
--
-- You would typically define instances for additional common type classes,
-- such as 'Eq', 'Ord', 'Show', etc.

------------------

-- $construction
--
-- #construction#
-- In order to be able to reason about how a given type of 'Applicative'
-- effects will be sequenced through a general 'Traversable' structure by its
-- 'traversable' and related methods, it is helpful to look more closely
-- at how a general 'traverse' method is implemented.  We'll look at how
-- general traversals are constructed primarily with a view to being able
-- to predict their behaviour as a user, even if you're not defining your
-- own 'Traversable' instances.
--
-- Traversable structures __@t a@__ are assembled incrementally from their
-- constituent parts, perhaps by prepending or appending individual elements of
-- type __@a@__, or, more generally, by recursively combining smaller composite
-- traversable building blocks that contain multiple such elements.
--
-- As in the [tree example](#tree) above, the components being combined are
-- typically pieced together by a suitable /constructor/, i.e. a function
-- taking two or more arguments that returns a composite value.
--
-- The 'traverse' method enriches simple incremental construction with
-- threading of 'Applicative' effects of some function __@g :: a -> f b@__.
--
-- The basic building blocks we'll use to model the construction of 'traverse'
-- are a hypothetical set of elementary functions, some of which may have
-- direct analogues in specific @Traversable@ structures.  For example, the
-- __@(':')@__ constructor is an analogue for lists of @prepend@ or the more
-- general @combine@.
--
-- > empty :: t a               -- build an empty container
-- > singleton :: a -> t a      -- build a one-element container
-- > prepend :: a -> t a -> t a -- extend by prepending a new initial element
-- > append  :: t a -> a -> t a -- extend by appending a new final element
-- > combine :: a1 -> a2 -> ... -> an -> t a -- combine multiple inputs
--
-- * An empty structure has no elements of type __@a@__, so there's nothing
--   to which __@g@__ can be applied, but since we need an output of type
--   __@f (t b)@__, we just use the 'pure' instance of __@f@__ to wrap an
--   empty of type __@t b@__:
--
--     > traverse _ (empty :: t a) = pure (empty :: t b)
--
--     With the List monad, /empty/ is __@[]@__, while with 'Maybe' it is
--     'Nothing'.  With __@Either e a@__ we have an /empty/ case for each
--     value of __@e@__:
--
--     > traverse _ (Left e :: Either e a) = pure $ (Left e :: Either e b)
--
-- * A singleton structure has just one element of type __@a@__, and
--   'traverse' can take that __@a@__, apply __@g :: a -> f b@__ getting an
--   __@f b@__, then __@fmap singleton@__ over that, getting an __@f (t b)@__
--   as required:
--
--     > traverse g (singleton a) = fmap singleton $ g a
--
--     Note that if __@f@__ is __@List@__ and __@g@__ returns multiple values
--     the result will be a list of multiple __@t b@__ singletons!
--
--     Since 'Maybe' and 'Either' are either empty or singletons, we have
--
--     > traverse _ Nothing = pure Nothing
--     > traverse g (Just a) = Just <$> g a
--
--     > traverse _ (Left e) = pure (Left e)
--     > traverse g (Right a) = Right <$> g a
--
--     For @List@, empty is __@[]@__ and @singleton@ is __@(:[])@__, so we have:
--
--     > traverse _ []  = pure []
--     > traverse g [a] = fmap (:[]) (g a)
--     >                = (:) <$> (g a) <*> traverse g []
--     >                = liftA2 (:) (g a) (traverse g [])
--
-- * When the structure is built by adding one more element via __@prepend@__
--   or __@append@__, traversal amounts to:
--
--     > traverse g (prepend a t0) = prepend <$> (g a) <*> traverse g t0
--     >                           = liftA2 prepend (g a) (traverse g t0)
--
--     > traverse g (append t0 a) = append <$> traverse g t0 <*> g a
--     >                          = liftA2 append (traverse g t0) (g a)
--
--     The origin of the combinatorial product when __@f@__ is @List@ should now
--     be apparent, when __@traverse g t0@__ has __@n@__ elements and __@g a@__
--     has __@m@__ elements, the /non-deterministic/ 'Applicative' instance of
--     @List@ will produce a result with __@m * n@__ elements.
--
-- * When combining larger building blocks, we again use __@('<*>')@__ to
--   combine the traversals of the components.  With bare elements __@a@__
--   mapped to __@f b@__ via __@g@__, and composite traversable
--   sub-structures transformed via __@traverse g@__:
--
--     > traverse g (combine a1 a2 ... an) =
--     >     combine <$> t1 <*> t2 <*> ... <*> tn
--     >   where
--     >      t1 = g a1          -- if a1 fills a slot of type @a@
--     >         = traverse g a1 -- if a1 is a traversable substructure
--     >      ... ditto for the remaining constructor arguments ...
--
-- The above definitions sequence the 'Applicative' effects of __@f@__ in the
-- expected order while producing results of the expected shape __@t@__.
--
-- For lists this becomes:
--
-- > traverse g [] = pure []
-- > traverse g (x:xs) = liftA2 (:) (g a) (traverse g xs)
--
-- The actual definition of 'traverse' for lists is an equivalent
-- right fold in order to facilitate list /fusion/.
--
-- > traverse g = foldr (\x r -> liftA2 (:) (g x) r) (pure [])

------------------

-- $advanced
--
-- #advanced#
-- In the sections below we'll examine some advanced choices of 'Applicative'
-- effects that give rise to very different transformations of @Traversable@
-- structures.
--
-- These examples cover the implementations of 'fmapDefault', 'foldMapDefault',
-- 'mapAccumL' and 'mapAccumR' functions illustrating the use of 'Identity',
-- 'Const' and stateful 'Applicative' effects.  The [ZipList](#ziplist) example
-- illustrates the use of a less-well known 'Applicative' instance for lists.
--
-- This is optional material, which is not essential to a basic understanding of
-- @Traversable@ structures.  If this is your first encounter with @Traversable@
-- structures, you can come back to these at a later date.

-- $coercion
--
-- #coercion#
-- Some of the examples make use of an advanced Haskell feature, namely
-- @newtype@ /coercion/.  This is done for two reasons:
--
-- * Use of 'coerce' makes it possible to avoid cluttering the code with
--   functions that wrap and unwrap /newtype/ terms, which at runtime are
--   indistinguishable from the underlying value.  Coercion is particularly
--   convenient when one would have to otherwise apply multiple newtype
--   constructors to function arguments, and then peel off multiple layers
--   of same from the function output.
--
-- * Use of 'coerce' can produce more efficient code, by reusing the original
--   value, rather than allocating space for a wrapped clone.
--
-- If you're not familiar with 'coerce', don't worry, it is just a shorthand
-- that, e.g., given:
--
-- > newtype Foo a = MkFoo { getFoo :: a }
-- > newtype Bar a = MkBar { getBar :: a }
-- > newtype Baz a = MkBaz { getBaz :: a }
-- > f :: Baz Int -> Bar (Foo String)
--
-- makes it possible to write:
--
-- > x :: Int -> String
-- > x = coerce f
--
-- instead of
--
-- > x = getFoo . getBar . f . MkBaz

------------------

-- $identity
--
-- #identity#
-- The simplest Applicative functor is 'Identity', which just wraps and unwraps
-- pure values and function application.  This allows us to define
-- 'fmapDefault':
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > import Data.Coercible (coerce)
-- >
-- > fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b
-- > fmapDefault = coerce (traverse @t @Identity @a @b)
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap terms via 'Identity' and 'runIdentity'.
--
-- As noted in [Overview](#overview), 'fmapDefault' can only be used to define
-- the requisite 'Functor' instance of a 'Traversable' structure when the
-- 'traverse' method is explicitly implemented.  An infinite loop would result
-- if in addition 'traverse' were defined in terms of 'sequenceA' and 'fmap'.

------------------

-- $stateful
--
-- #stateful#
-- Applicative functors that thread a changing state through a computation are
-- an interesting use-case for 'traverse'.  The 'mapAccumL' and 'mapAccumR'
-- functions in this module are each defined in terms of such traversals.
--
-- We first define a simplified (not a monad transformer) version of
-- 'Control.Monad.Trans.State.State' that threads a state __@s@__ through a
-- chain of computations left to right.  Its @('<*>')@ operator passes the
-- input state first to its left argument, and then the resulting state is
-- passed to its right argument, which returns the final state.
--
-- > newtype StateL s a = StateL { runStateL :: s -> (s, a) }
-- >
-- > instance Functor (StateL s) where
-- >     fmap f (StateL kx) = StateL $ \ s ->
-- >         let (s', x) = kx s in (s', f x)
-- >
-- > instance Applicative (StateL s) where
-- >     pure a = StateL $ \s -> (s, a)
-- >     (StateL kf) <*> (StateL kx) = StateL $ \ s ->
-- >         let { (s',  f) = kf s
-- >             ; (s'', x) = kx s' } in (s'', f x)
-- >     liftA2 f (StateL kx) (StateL ky) = StateL $ \ s ->
-- >         let { (s',  x) = kx s
-- >             ; (s'', y) = ky s' } in (s'', f x y)
--
-- With @StateL@, we can define 'mapAccumL' as follows:
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > mapAccumL :: forall t s a b. Traversable t
-- >           => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
-- > mapAccumL g s ts = coerce (traverse @t @(StateL s) @a @b) (flip g) ts s
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@newtype@__ terms.
--
-- The type of __@flip g@__ is coercible to __@a -> StateL b@__, which makes it
-- suitable for use with 'traverse'.  As part of the Applicative
-- [construction](#construction) of __@StateL (t b)@__ the state updates will
-- thread left-to-right along the sequence of elements of __@t a@__.
--
-- While 'mapAccumR' has a type signature identical to 'mapAccumL', it differs
-- in the expected order of evaluation of effects, which must take place
-- right-to-left.
--
-- For this we need a variant control structure @StateR@, which threads the
-- state right-to-left, by passing the input state to its right argument and
-- then using the resulting state as an input to its left argument:
--
-- > newtype StateR s a = StateR { runStateR :: s -> (s, a) }
-- >
-- > instance Functor (StateR s) where
-- >     fmap f (StateR kx) = StateR $ \s ->
-- >         let (s', x) = kx s in (s', f x)
-- >
-- > instance Applicative (StateR s) where
-- >     pure a = StateR $ \s -> (s, a)
-- >     (StateR kf) <*> (StateR kx) = StateR $ \ s ->
-- >         let { (s',  x) = kx s
-- >             ; (s'', f) = kf s' } in (s'', f x)
-- >     liftA2 f (StateR kx) (StateR ky) = StateR $ \ s ->
-- >         let { (s',  y) = ky s
-- >             ; (s'', x) = kx s' } in (s'', f x y)
--
-- With @StateR@, we can define 'mapAccumR' as follows:
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > mapAccumR :: forall t s a b. Traversable t
-- >           => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
-- > mapAccumR g s0 ts = coerce (traverse @t @(StateR s) @a @b) (flip g) ts s0
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@newtype@__ terms.
--
-- Various stateful traversals can be constructed from 'mapAccumL' and
-- 'mapAccumR' for suitable choices of @g@, or built directly along similar
-- lines.

------------------

-- $phantom
--
-- #phantom#
-- The 'Const' Functor enables applications of 'traverse' that summarise the
-- input structure to an output value without constructing any output values
-- of the same type or shape.
--
-- As noted [above](#overview), the @Foldable@ superclass constraint is
-- justified by the fact that it is possible to construct 'foldMap', 'foldr',
-- etc., from 'traverse'.  The technique used is useful in its own right, and
-- is explored below.
--
-- A key feature of folds is that they can reduce the input structure to a
-- summary value. Often neither the input structure nor a mutated clone is
-- needed once the fold is computed, and through list fusion the input may not
-- even have been memory resident in its entirety at the same time.
--
-- The 'traverse' method does not at first seem to be a suitable building block
-- for folds, because its return value __@f (t b)@__ appears to retain mutated
-- copies of the input structure.  But the presence of __@t b@__ in the type
-- signature need not mean that terms of type __@t b@__ are actually embedded
-- in __@f (t b)@__.  The simplest way to elide the excess terms is by basing
-- the Applicative functor used with 'traverse' on 'Const'.
--
-- Not only does __@Const a b@__ hold just an __@a@__ value, with the __@b@__
-- parameter merely a /phantom/ type, but when __@m@__ has a 'Monoid' instance,
-- __@Const m@__ is an 'Applicative' functor:
--
-- > import Data.Coerce (coerce)
-- > newtype Const a b = Const { getConst :: a } deriving (Eq, Ord, Show) -- etc.
-- > instance Functor (Const m) where fmap = const coerce
-- > instance Monoid m => Applicative (Const m) where
-- >    pure _   = Const mempty
-- >    (<*>)    = coerce (mappend :: m -> m -> m)
-- >    liftA2 _ = coerce (mappend :: m -> m -> m)
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@newtype@__ terms.
--
-- We can therefore define a specialisation of 'traverse':
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > traverseC :: forall t a m. (Monoid m, Traversable t)
-- >           => (a -> Const m ()) -> t a -> Const m (t ())
-- > traverseC = traverse @t @(Const m) @a @()
--
-- For which the Applicative [construction](#construction) of 'traverse'
-- leads to:
--
-- prop> null ts ==> traverseC g ts = Const mempty
-- prop> traverseC g (prepend x xs) = Const (g x) <> traverseC g xs
--
-- In other words, this makes it possible to define:
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > foldMapDefault :: forall t a m. (Monoid m, Traversable t) => (a -> m) -> t a -> m
-- > foldMapDefault = coerce (traverse @t @(Const m) @a @())
--
-- Which is sufficient to define a 'Foldable' superclass instance:
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@newtype@__ terms.
--
-- > instance Traversable t => Foldable t where foldMap = foldMapDefault
--
-- It may however be instructive to also directly define candidate default
-- implementations of 'foldr' and 'foldl'', which take a bit more machinery
-- to construct:
--
-- > {-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
-- > import Data.Coerce (coerce)
-- > import Data.Functor.Const (Const(..))
-- > import Data.Semigroup (Dual(..), Endo(..))
-- > import GHC.Exts (oneShot)
-- >
-- > foldrDefault :: forall t a b. Traversable t
-- >              => (a -> b -> b) -> b -> t a -> b
-- > foldrDefault f z = \t ->
-- >     coerce (traverse @t @(Const (Endo b)) @a @()) f t z
-- >
-- > foldlDefault' :: forall t a b. Traversable t => (b -> a -> b) -> b -> t a -> b
-- > foldlDefault' f z = \t ->
-- >     coerce (traverse @t @(Const (Dual (Endo b))) @a @()) f' t z
-- >   where
-- >     f' :: a -> b -> b
-- >     f' a = oneShot $ \ b -> b `seq` f b a
--
-- In the above we're using the __@'Data.Monoid.Endo' b@__ 'Monoid' and its
-- 'Dual' to compose a sequence of __@b -> b@__ accumulator updates in either
-- left-to-right or right-to-left order.
--
-- The use of 'seq' in the definition of __@foldlDefault'@__ ensures strictness
-- in the accumulator.
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@newtype@__ terms.
--
-- The 'GHC.Exts.oneShot' function gives a hint to the compiler that aids in
-- correct optimisation of lambda terms that fire at most once (for each
-- element __@a@__) and so should not try to pre-compute and re-use
-- subexpressions that pay off only on repeated execution.  Otherwise, it is
-- just the identity function.

------------------

-- $ziplist
--
-- #ziplist#
-- As a warm-up for looking at the 'ZipList' 'Applicative' functor, we'll first
-- look at a simpler analogue.  First define a fixed width 2-element @Vec2@
-- type, whose 'Applicative' instance combines a pair of functions with a pair of
-- values by applying each function to the corresponding value slot:
--
-- > data Vec2 a = Vec2 a a
-- > instance Functor Vec2 where
-- >     fmap f (Vec2 a b) = Vec2 (f a) (f b)
-- > instance Applicative Vec2 where
-- >     pure x = Vec2 x x
-- >     liftA2 f (Vec2 a b) (Vec2 p q) = Vec2 (f a p) (f b q)
-- > instance Foldable Vec2 where
-- >     foldr f z (Vec2 a b) = f a (f b z)
-- >     foldMap f (Vec2 a b) = f a <> f b
-- > instance Traversable Vec2 where
-- >     traverse f (Vec2 a b) = Vec2 <$> f a <*> f b
--
-- Along with a similar definition for fixed width 3-element vectors:
--
-- > data Vec3 a = Vec3 a a a
-- > instance Functor Vec3 where
-- >     fmap f (Vec3 x y z) = Vec3 (f x) (f y) (f z)
-- > instance Applicative Vec3 where
-- >     pure x = Vec3 x x x
-- >     liftA2 f (Vec3 p q r) (Vec3 x y z) = Vec3 (f p x) (f q y) (f r z)
-- > instance Foldable Vec3 where
-- >     foldr f z (Vec3 a b c) = f a (f b (f c z))
-- >     foldMap f (Vec3 a b c) = f a <> f b <> f c
-- > instance Traversable Vec3 where
-- >     traverse f (Vec3 a b c) = Vec3 <$> f a <*> f b <*> f c
--
-- With the above definitions, @'sequenceA'@ (same as @'traverse' 'id'@) acts
-- as a /matrix transpose/ operation on @Vec2 (Vec3 Int)@ producing a
-- corresponding @Vec3 (Vec2 Int)@:
--
-- Let __@t = Vec2 (Vec3 1 2 3) (Vec3 4 5 6)@__ be our 'Traversable' structure,
-- and __@g = id :: Vec3 Int -> Vec3 Int@__ be the function used to traverse
-- __@t@__.  We then have:
--
-- > traverse g t = Vec2 <$> (Vec3 1 2 3) <*> (Vec3 4 5 6)
-- >              = Vec3 (Vec2 1 4) (Vec2 2 5) (Vec2 3 6)
--
-- This construction can be generalised from fixed width vectors to variable
-- length lists via 'Control.Applicative.ZipList'.  This gives a transpose
-- operation that works well for lists of equal length.  If some of the lists
-- are longer than others, they're truncated to the longest common length.
--
-- We've already looked at the standard 'Applicative' instance of @List@ for
-- which applying __@m@__ functions __@f1, f2, ..., fm@__ to __@n@__ input
-- values __@a1, a2, ..., an@__ produces __@m * n@__ outputs:
--
-- >>> :set -XTupleSections
-- >>> [("f1",), ("f2",), ("f3",)] <*> [1,2]
-- [("f1",1),("f1",2),("f2",1),("f2",2),("f3",1),("f3",2)]
--
-- There are however two more common ways to turn lists into 'Applicative'
-- control structures.  The first is via __@'Const' [a]@__, since lists are
-- monoids under concatenation, and we've already seen that __@'Const' m@__ is
-- an 'Applicative' functor when __@m@__ is a 'Monoid'.  The second, is based
-- on 'Data.List.zipWith', and is called 'Control.Applicative.ZipList':
--
-- > {-# LANGUAGE GeneralizedNewtypeDeriving #-}
-- > newtype ZipList a = ZipList { getZipList :: [a] }
-- >     deriving (Show, Eq, ..., Functor)
-- >
-- > instance Applicative ZipList where
-- >     liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith f xs ys
-- >     pure x = repeat x
--
-- The 'liftA2' definition is clear enough, instead of applying __@f@__ to each
-- pair __@(x, y)@__ drawn independently from the __@xs@__ and __@ys@__, only
-- corresponding pairs at each index in the two lists are used.
--
-- The definition of 'pure' may look surprising, but it is needed to ensure
-- that the instance is lawful:
--
-- prop> liftA2 f (pure x) ys == fmap (f x) ys
--
-- Since __@ys@__ can have any length, we need to provide an infinite supply
-- of __@x@__ values in __@pure x@__ in order to have a value to pair with
-- each element __@y@__.
--
-- When 'Control.Applicative.ZipList' is the 'Applicative' functor used in the
-- [construction](#construction) of a traversal, a ZipList holding a partially
-- built structure with __@m@__ elements is combined with a component holding
-- __@n@__ elements via 'zipWith', resulting in __@min m n@__ outputs!
--
-- Therefore 'traverse' with __@g :: a -> ZipList b@__ will produce a @ZipList@
-- of __@t b@__ structures whose element count is the minimum length of the
-- ZipLists __@g a@__ with __@a@__ ranging over the elements of __@t@__.  When
-- __@t@__ is empty, the length is infinite (as expected for a minimum of an
-- empty set).
--
-- If the structure __@t@__ holds values of type __@ZipList a@__, we can use
-- the identity function __@id :: ZipList a -> ZipList a@__ for the first
-- argument of 'traverse':
--
-- > traverse (id :: ZipList a -> ZipList a) :: t (ZipList a) -> ZipList (t a)
--
-- The number of elements in the output @ZipList@ will be the length of the
-- shortest @ZipList@ element of __@t@__.  Each output __@t a@__ will have the
-- /same shape/ as the input __@t (ZipList a)@__, i.e. will share its number of
-- elements.
--
-- If we think of the elements of __@t (ZipList a)@__ as its rows, and the
-- elements of each individual @ZipList@ as the columns of that row, we see
-- that our traversal implements a /transpose/ operation swapping the rows
-- and columns of __@t@__, after first truncating all the rows to the column
-- count of the shortest one.
--
-- Since in fact __@'traverse' id@__ is just 'sequenceA' the above boils down
-- to a rather concise definition of /transpose/, with [coercion](#coercion)
-- used to implicitly wrap and unwrap the @ZipList@ @newtype@ as needed, giving
-- a function that operates on a list of lists:
--
-- >>> {-# LANGUAGE ScopedTypeVariables #-}
-- >>> import Control.Applicative (ZipList(..))
-- >>> import Data.Coerce (coerce)
-- >>>
-- >>> transpose :: forall a. [[a]] -> [[a]]
-- >>> transpose = coerce (sequenceA :: [ZipList a] -> ZipList [a])
-- >>>
-- >>> transpose [[1,2,3],[4..],[7..]]
-- [[1,4,7],[2,5,8],[3,6,9]]
--
-- The use of [coercion](#coercion) avoids the need to explicitly wrap and
-- unwrap __@ZipList@__ terms.

------------------

-- $laws
--
-- #laws#
-- 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' ('Data.Functor.Compose.Compose' . 'fmap' g . f)
--     = 'Data.Functor.Compose.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' 'Data.Functor.Compose.Compose'
--     = 'Data.Functor.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.
--
-- @
-- t ('pure' x) = 'pure' x
-- t (f '<*>' x) = t f '<*>' t x
-- @
--
-- and the identity functor 'Identity' and composition functors
-- 'Data.Functor.Compose.Compose' are from "Data.Functor.Identity" and
-- "Data.Functor.Compose".
--
-- A result of the naturality law is a purity law for 'traverse'
--
-- @'traverse' 'pure' = 'pure'@
--
-- 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, 'Data.Foldable.foldMap' should be
--    equivalent to traversal with a constant applicative functor
--    ('foldMapDefault').
--
-- Note: the 'Functor' superclass means that (in GHC) Traversable structures
-- cannot impose any constraints on the element type.  A Haskell implementation
-- that supports constrained functors could make it possible to define
-- constrained @Traversable@ structures.

------------------

-- $also
--
--  * \"The Essence of the Iterator Pattern\",
--    by Jeremy Gibbons and Bruno Oliveira,
--    in /Mathematically-Structured Functional Programming/, 2006, online at
--    <http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator>.
--
--  * \"Applicative Programming with Effects\",
--    by Conor McBride and Ross Paterson,
--    /Journal of Functional Programming/ 18:1 (2008) 1-13, online at
--    <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
--
--  * \"An Investigation of the Laws of Traversals\",
--    by Mauro Jaskelioff and Ondrej Rypacek,
--    in /Mathematically-Structured Functional Programming/, 2012, online at
--    <http://arxiv.org/pdf/1202.2919>.