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