Adding `mapAccumL'` to `Data.Traversable` (re-exported via `Data.List`)

# Adding `mapAccumL'` to `Data.Traversable` (re-exported via `Data.List`)

Problem: `mapAccumL` can be used to run a state machine over a traversable data structure, perhaps primarily lists (at least for me). It may be expected from the user that this function be lazy so one could use `fst $ mapAccumL f s list` to get the state or `snd $ mapAccumL f s list` to get the output list. Although one can build their own State stacks and use a traverse on that stack to get the same effect, it is much convenient to provide and use this handy pure function for plenty of operations.

From a user perspective of this `mapAccumL` function, there seems to be no obvious way to get the correct memory behavior, if one wants to get the state in a bounded memory without consuming the output data structure.

(So, the problem is not something is unviable or wrong about `traverse / mapAccumL`, but the lack of a safer default `mapAccumL'` for certain types of tasks, especially when operating on linear traversable data structures like lists.)

```haskell
module Main where

import qualified Data.List as L
import System.Environment (getArgs)

main :: IO ()
main = do
args <- getArgs
mapM_ print args
case args of
["lazy" , "1"] -> print $ fst $ L.mapAccumL (\ s x -> (s + 1, x)) 0 [1..10000000]
["lazy" , "2"] -> print $ sum $ snd $ L.mapAccumL (\ s x -> (s + 1, x)) 0 [1..10000000]
["strict", "1"] -> print $ fst $ L.mapAccumL (\ !s x -> (s + 1, x)) 0 [1..10000000]
["strict", "2"] -> print $ sum $ snd $ L.mapAccumL (\ !s x -> (s + 1, x)) 0 [1..10000000]
```

Whether you add `!s` or not, you cannot get the state only without blowing up memory.

```bash
ghc -O --make mapAccum.hs && ./mapAccum lazy 1 +RTS -s && ./mapAccum lazy 2 +RTS -s && ./mapAccum strict 1 +RTS -s && ./mapAccum strict 2 +RTS -s
```

```
Loaded package environment from /home/eiko/.ghc/x86_64-linux-9.12.2/environments/default
[1 of 2] Compiling Main ( mapAccum.hs, mapAccum.o ) [Source file changed]
[2 of 2] Linking mapAccum [Objects changed]
"lazy"
"1"
10000000
2,172,389,480 bytes allocated in the heap
1,295,230,920 bytes copied during GC
453,422,920 bytes maximum residency (10 sample(s))
3,537,080 bytes maximum slop
675 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 514 colls, 0 par 0.262s 0.264s 0.0005s 0.0017s
Gen 1 10 colls, 0 par 0.441s 0.445s 0.0445s 0.1388s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.212s ( 0.213s elapsed)
GC time 0.702s ( 0.709s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.915s ( 0.922s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 10,246,331,076 bytes per MUT second

Productivity 23.2% of total user, 23.1% of total elapsed

"lazy"
"2"
50000005000000
1,840,056,664 bytes allocated in the heap
940,279,496 bytes copied during GC
233,596,320 bytes maximum residency (9 sample(s))
3,725,920 bytes maximum slop
465 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 435 colls, 0 par 0.112s 0.114s 0.0003s 0.0009s
Gen 1 9 colls, 0 par 0.291s 0.293s 0.0326s 0.1384s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.099s ( 0.099s elapsed)
GC time 0.403s ( 0.408s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.503s ( 0.508s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 18,553,753,853 bytes per MUT second

Productivity 19.7% of total user, 19.6% of total elapsed

"strict"
"1"
10000000
3,462,082,040 bytes allocated in the heap
3,420,414,936 bytes copied during GC
872,861,856 bytes maximum residency (10 sample(s))
7,834,536 bytes maximum slop
1565 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 823 colls, 0 par 0.821s 0.827s 0.0010s 0.0021s
Gen 1 10 colls, 0 par 1.006s 1.015s 0.1015s 0.3881s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.365s ( 0.366s elapsed)
GC time 1.827s ( 1.843s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 2.193s ( 2.209s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 9,480,287,068 bytes per MUT second

Productivity 16.7% of total user, 16.6% of total elapsed

"strict"
"2"
50000005000000
3,040,057,032 bytes allocated in the heap
103,520 bytes copied during GC
44,328 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
6 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 750 colls, 0 par 0.001s 0.001s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.229s ( 0.230s elapsed)
GC time 0.001s ( 0.002s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.231s ( 0.232s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 13,251,671,983 bytes per MUT second

Productivity 99.2% of total user, 99.2% of total elapsed
```

# Analysis

The problem can be illustrated via the following equational reasoning:

```haskell
fst $ mapAccum f 0 [1..10000000]
= mapAccum f (0 `f` 1) [2..10000000]
= mapAccum f ((0 `f` 1) `f` 2) [3..10000000]
= mapAccum f (((0 `f` 1) `f` 2) `f` 3) [4..10000000]
= ...
```

We can see that the problem is the `foldl`-like expression inside, we could replace it by a `foldl'`-like evaluation.

# Proposed Solution

We can add a `mapAccumL'` function that uses a strict State. Currently it uses an internal `Applicative` functor `StateL`. We can add a `StateL'` functor that is strict in the state, like this:

```haskell
-- | copied the implementation of 'StateL'
newtype StateL' s a = StateL' { runStateL :: s -> (s, a) }

instance Functor (StateL' s) where
fmap f (StateL' k) = StateL' $ \ s -> let !(!s', v) = k s in (s', f v)

instance Applicative (StateL' s) where
pure x = StateL' (\s -> (s, x))
StateL' kf <*> StateL' kv = StateL' $ \ s ->
let !(!s', f) = kf s
(s'', v) = kv s'
in (s'', f v)
liftA2 f (StateL' kx) (StateL' ky) = StateL' $ \s ->
let !(!s', x) = kx s
(s'', y) = ky s'
in (s'', f x y)

-- | The same as 'mapAccumL', but its state is evaluated strictly.
-- the implmentation is the same as 'mapAccumL'
mapAccumL' :: forall t s a b. Traversable t
=> (s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL' f s t = coerce (traverse @t @(StateL' s) @a @b) (flip f) t s
```

# Improvements

With either one of the above `mapAccumL'` implementations, we can get the correct memory behavior:

```haskell
module Main where

import qualified Data.List as L
import Data.Coerce
import System.Environment (getArgs)

-- | copied the implementation of 'StateL'
newtype StateL' s a = StateL' { runStateL :: s -> (s, a) }

instance Functor (StateL' s) where
fmap f (StateL' k) = StateL' $ \ s -> let !(!s', v) = k s in (s', f v)

instance Applicative (StateL' s) where
pure x = StateL' (\s -> (s, x))
StateL' kf <*> StateL' kv = StateL' $ \ s ->
let !(!s', f) = kf s
(s'', v) = kv s'
in (s'', f v)
liftA2 f (StateL' kx) (StateL' ky) = StateL' $ \s ->
let !(!s', x) = kx s
(s'', y) = ky s'
in (s'', f x y)

main :: IO ()
main = do
args <- getArgs
mapM_ print args
case args of
["lazy" , "1"] -> print $ fst $ mapAccumL' (\ s x -> (s + 1, x)) 0 [1..10000000]
["lazy" , "2"] -> print $ sum $ snd $ mapAccumL' (\ s x -> (s + 1, x)) 0 [1..10000000]
["strict", "1"] -> print $ fst $ mapAccumL' (\ !s x -> (s + 1, x)) 0 [1..10000000]
["strict", "2"] -> print $ sum $ snd $ mapAccumL' (\ !s x -> (s + 1, x)) 0 [1..10000000]

-- | The same as 'mapAccumL', but its state is evaluated strictly:
-- it forces the accumulator component to WHNF after each step, but
-- does not force the produced element.
mapAccumL' :: forall t s a b. Traversable t
=> (s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL' f s t = coerce (traverse @t @(StateL' s) @a @b) (flip f) t s
```

```bash
ghc -O --make mapAccum.hs && ./mapAccum lazy 1 +RTS -s && ./mapAccum lazy 2 +RTS -s && ./mapAccum strict 1 +RTS -s && ./mapAccum strict 2 +RTS -s
```

```
Loaded package environment from /home/eiko/.ghc/x86_64-linux-9.12.2/environments/default
[1 of 2] Compiling Main ( mapAccum.hs, mapAccum.o ) [Source file changed]
[2 of 2] Linking mapAccum [Objects changed]
"lazy"
"1"
10000000
1,600,089,192 bytes allocated in the heap
35,648 bytes copied during GC
60,224 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
6 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 389 colls, 0 par 0.001s 0.001s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.111s ( 0.111s elapsed)
GC time 0.001s ( 0.001s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.112s ( 0.113s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 14,439,624,293 bytes per MUT second

Productivity 98.8% of total user, 98.8% of total elapsed

"lazy"
"2"
50000005000000
1,760,056,648 bytes allocated in the heap
54,008 bytes copied during GC
44,328 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
6 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 423 colls, 0 par 0.001s 0.001s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.105s ( 0.110s elapsed)
GC time 0.001s ( 0.001s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.106s ( 0.111s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 16,696,264,408 bytes per MUT second

Productivity 99.2% of total user, 99.1% of total elapsed

"strict"
"1"
10000000
1,600,089,592 bytes allocated in the heap
35,744 bytes copied during GC
60,224 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
6 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 389 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.110s ( 0.110s elapsed)
GC time 0.001s ( 0.001s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.111s ( 0.111s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 14,572,050,817 bytes per MUT second

Productivity 99.1% of total user, 99.1% of total elapsed

"strict"
"2"
50000005000000
1,760,057,048 bytes allocated in the heap
54,104 bytes copied during GC
44,328 bytes maximum residency (2 sample(s))
29,400 bytes maximum slop
6 MiB total memory in use (0 MiB lost due to fragmentation)

Tot time (elapsed) Avg pause Max pause
Gen 0 423 colls, 0 par 0.000s 0.001s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s

INIT time 0.000s ( 0.000s elapsed)
MUT time 0.107s ( 0.107s elapsed)
GC time 0.001s ( 0.001s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.108s ( 0.108s elapsed)

%GC time 0.0% (0.0% elapsed)

Alloc rate 16,464,903,128 bytes per MUT second

Productivity 99.1% of total user, 99.1% of total elapsed
```

This version also works without any optimizations (maximum residency stays the same without -O, only total allocation differs).

# Impact

This is a non-breaking change since it only adds a function.

# Value

I would argue that this function brings user much more predictability with less surprise since in Haskell, stateful transformations are almost always best strictly evaluated. Moreover the function can be composed in anyway the user expects a 'lazy' function would do, it might be worth adding. Whether `mapAccumR'` or `mapAccumM'` could be worth adding can be discussed in the future as well. Personally I think `mapAccumL'` could be a safer default for users of `Data.List`.

Start by reading the existing mapAccumL implementation in Data.Traversable and its re-export through Data.List, including the internal StateL applicative. Review the issue discussion around the proposed strict StateL' design and API addition. Done means the committee agrees on the interface and semantics, with the implementation and re-export covered consistently.

Written by the indexing model from the issue text.