[Haskell-cafe] Minor issue with mapAccumR

Cale Gibbard cgibbard at gmail.com
Tue Feb 5 00:03:38 EST 2008


I'm not sure whether this would be considered worth fixing right away,
or if we should wait until some other major compatibility breaking
language change to fix it, but it appears that somehow the parameters
to the function passed to mapAccumR are flipped relative to their
natural order.

To show what I mean, here is some code:

Prelude Data.List> mapAccumR (\x y -> (concat ["(f ",x," ",y,")"],
concat ["(g ",x," ",y,")"])) "z" ["1","2","3"]
("(f (f (f z 3) 2) 1)",["(g (f (f z 3) 2) 1)","(g (f z 3) 2)","(g z 3)"])

You can see here that the list is flipped over in the process, even
though the right fold structure is there, it ends up looking like a
left fold over the reverse of the list.

One would want the law:

fst . mapAccumR f z = foldr (fst . f) z

to be true, but instead we have:

fst . mapAccumR (flip f) z = foldr (fst . f) z

You can see that structurally if we flip the parameters in the above example:

Prelude Data.List> mapAccumR (\y x -> (concat ["(f ",x," ",y,")"],
concat ["(g ",x," ",y,")"])) "z" ["1","2","3"]
("(f 1 (f 2 (f 3 z)))",["(g 1 (f 2 (f 3 z)))","(g 2 (f 3 z))","(g 3 z)"])

I also have some diagrams on
http://cale.yi.org/index.php/Fold_Diagrams (near the end) displaying
the difference, and that's where I first noticed it.

Are many people using mapAccumR? How much would it hurt to change it?

 - Cale


More information about the Haskell-Cafe mailing list