proposal #2461: add Traversable generalizations of mapAccumL and mapAccumR

[David Menendez]

On Tue, Jul 22, 2008 at 12:12 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> The proposal is to add the following functions to Data.Traversable,
> generalizing the list versions in Data.List:
>
>    -- |The 'mapAccumL' function behaves like a combination of 'fmap'
>    -- and '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.
>    mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
>
>    -- |The 'mapAccumR' function behaves like a combination of 'fmap'
>    -- and '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.
>    mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
>
> These functions are handy for things like labelling trees, zipping, etc.

I take it these would be implemented using a state transformer monad?
That is, something along these lines:

mapAccumL f a tb = runState (mapM (\b -> State (\a -> f a b)) tb) a

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.



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)

It shows up in at least one of the early applicative functor papers,
and it seems like it would be handy for generalizing things like
mapAccumL vs mapAccumR.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>