Re: proposal #2461: add Traversable generalizations of mapAccumL and mapAccumR

On Tue, Jul 22, 2008 at 09:49:29PM -0400, David Menendez wrote:

On Tue, Jul 22, 2008 at 12:12 PM, Ross Paterson 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.