proposal #2461: add Traversable generalizations of mapAccumL and mapAccumR

[Ross Paterson]

On Tue, Jul 22, 2008 at 09:49:29PM -0400, David Menendez wrote:
> On Tue, Jul 22, 2008 at 12:12 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> >    mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
> >
> >    mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
> 
> I take it these would be implemented using a state transformer monad?

Yes (actually the applicative functor and its mirror image).  Full code
in the patch attached to the ticket.

> Presumably, we don't want to include every possible specialization of
> 'traverse', but I can imagine it being awkward to simulate mapAccumL/R
> with a state monad if the actual code is short.

Indeed, it's convenient for numbering elements of a container from the
left or from the right:

	mapAccumL (\ n x -> (n+1, (n,x))) 0
	mapAccumR (\ n x -> (n+1, (n,x))) 0

zipping with a sufficiently long list:

	mapAccumL (\ (x:xs) y -> (xs, (x,y))) xs0

and the list versions of these functions are already in Data.List
(and the Haskell 98 List module).

> Incidentally, is there a Backward applicative functor transfomer
> defined anywhere?
> 
>     newtype Backward f a = Backward { runBackward :: f a } deriving Functor
> 
>     instance Applicative f => Applicative (Backward f) where
>         pure = Backward . pure
>         (Backward f) <*> (Backward a) = Backward (f <**> a)

Probably in Conal or Edward Kmett's libraries.  Data.Monoid has the
Monoid version.