Proposal: Strict scanl, scanl1 and mapAccumL

[Bas van Dijk]

On 12 November 2012 11:17, Henning Thielemann
<lemming at henning-thielemann.de> wrote:
> My impression is that making 'seq' available as function without a typeclass
> constraint was a step in the wrong direction. Then foldl' and friends were
> the second step in the wrong direction and scanl' would be the third step.
> For 'seq' I would propose we first start with a cleanly typed 'seq' and base
> foldl' functions on this function instead of the built-in 'seq'.

I think I agree that putting seq in a type class would have been
better (especially since we can now derive things generically).
However if we are going to change this we have to change a lot of code
anyway. Why not add these strict functions now and change all of them
later (incl. all the strict functions in containers) when the Seq type
class gets added (if that ever happens...)?

> But I
> assume that most of the time where foldl' is used, actually a deepseq-foldl'
> is meant. I have often seen foldl' in Haskell library code that had not the
> intended effect since the accumulator was a lazy pair or a Map.

If your accumulator in foldl' is a lazy pair you should just seq the
new elements before returning the pair. Not doing that is just silly.
I don't see the need for deepseq there.

In case your accumulator is a Map you really want to use foldl'. For
example the following program results in a stack space overflow (when
compiled without optimizations):

import qualified Data.Map as M
main = print
     $ M.size
     $ foldl (\m i -> M.insert i i m) M.empty
       [1..1000000]

With foldl' it doesn't.

Even if you have a large enough stack (-k128m) this program will still
allocate a big part of your heap (to store all the intermediate
'M.insert i i m' thunks) if I'm not mistaken. foldl' also doesn't do
that.

Cheers,

Bas