mapAccumR

mapAccumR is a higher-order function in Haskell's Data.List module that maps a function over a list while threading an accumulator from right to left. It returns a pair consisting of the final accumulator and the list of mapped results. The function and the accumulator are both updated as the mapping proceeds from the end of the list toward the front, but the resulting list is produced in the original left-to-right order.

The type signature is mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]). The first argument is a function that, given the current accumulator and an element, produces a new accumulator and a mapped value. The second argument provides the initial accumulator, and the third is the input list. The final accumulator reflects all updates, while the produced list of y-values maintains the original element order.

Example:

mapAccumR (\acc x -> let acc' = acc + x in (acc', acc')) 0 [1,2,3]

yields (6, [6,5,3])

This demonstrates the right-to-left threading of the accumulator: the first output element corresponds to the total sum after processing all elements to its right.

mapAccumR is the right-to-left counterpart of mapAccumL, which threads the accumulator from left to right. Both functions are part of Data.List and are useful when the computation for each element depends on the accumulated state formed from the elements to its right (or left, for mapAccumL). They are lazy in their structure, producing results as needed.