base-4.22.0.0: src/Data/Traversable.hs
{-# 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
-- $setup
-- >>> import Prelude
-- >>> import Data.Maybe
-- >>> import Data.Either
-- >>> import qualified Data.List as List
-- >>> :set -XExplicitForAll
-- $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> List.length (mapM g ts) == List.product (fmap (List.length . g) ts)
--
-- For example:
--
-- >>> List.length $ mapM (\n -> [1..n]) [1..6]
-- 720
-- >>> List.product $ List.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:
--
-- >>> :set -XScopedTypeVariables
-- >>> import Control.Applicative (ZipList(..))
-- >>> import Data.Coerce (coerce)
-- >>>
-- >>> :{
-- >>> let
-- >>> transpose :: forall a. [[a]] -> [[a]]
-- >>> transpose = coerce (sequenceA :: [ZipList a] -> ZipList [a])
-- >>> in 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>.