proposal #2461: add Traversable generalizations of mapAccumL
and mapAccumR
David Menendez
dave at zednenem.com
Tue Jul 22 21:49:29 EDT 2008
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/>
More information about the Libraries
mailing list