The function traverse takes an element and a map, and returns another element and a new (updated) map.

Given a list of elements xs0 and an initial map m0, I need to apply traverse to each element of the list while passing in the updated map to each new invocation of traverse, to produce a list of resulting elements and the last returned map:

foldr (\x (xs, m) -> let (x', m') = traverse x m
                     in (x':xs, m')) ([], m0) xs0

Is there a way to reduce all this clutter and use prelude as much as possible?

  • 1
    \$\begingroup\$ Are you using the standard traverse from the Traversable class, or something else? If it's something else, what's its type? And for that matter, what's the type of the full expression? \$\endgroup\$ – Carl Apr 17 '17 at 6:06

You pretty much want mapAccumR, except that one has all of the argument orders and pair orders backwards, or the State monad, except that one passes its state to the right. We can define our own mapAccumR:

mapAccumR :: (a -> s -> (b, s)) -> [a] -> s -> ([b], s)
mapAccumR f as s = foldr (\a (bs, s') -> let (b, s'') = f a s' in (b:bs, s'')) ([], s) as

As you can see, foldr also has its argument order wrong.

Now your code is mapAccumR traverse, except that you had the argument order wrong at the end there. :)

This implementation of mapAccumR is almost identical to your code, but the average reader will have heard of mapAccumR and the average stackoverflow voter evidently finds its code confusing out of context.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.