On Tue, Jul 22, 2008 at 12:12 PM, Ross Paterson <ross@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@zednenem.com> <http://www.eyrie.org/~zednenem/>