Proposal: accum and accumArray strictness

[David Feuer]

The documentation for accumArray is currently broken [*]. According to
the documentation:

According to the documentation,

If the accumulating function is strict, then 'accumArray' is strict in
the values, as well as the indices, in the association list. Thus,
unlike ordinary arrays built with 'array', accumulated arrays should
not in general be recursive.

I believe that purported strictness is desirable, because it prevents
thunks from accumulating when we use the passed function. But the
strictness *isn't really there*. accumArray never forces any values
whatsoever! The same is true of accum, but that function does not
document its strictness.

I propose that we change both the implementation and documentation.

For accumArray, I think we should say that the resulting array is
strict in the initial value and in each result of applying the
accumulating function, and indicate that each element of the resulting
array will be in WHNF.

For accum, I think we should say that the resulting array is strict in
each value in the initial array and in each result of applying the
accumulating function, and indicate that each element of the resulting
array will be in WHNF.

We thereby guarantee that we can accumulate strictly, which is
important for performance, and I think being strict in the initial
value(s) makes for simpler reasoning than only being strict in the
results of the combining function.

[*] https://ghc.haskell.org/trac/ghc/ticket/14785

David Feuer

[David Feuer]

Actually, let me take part of that back. We may not want accum to be
strict in the initial values. I don't believe we currently do anything
to avoid copying an array if it's used in a single-threaded fashion,
but if we did then being strict in the initial values would jack up
the price too much. So I think maybe we should do the uglier thing of
only forcing results of the accumulating functions. But should we be
strict in the initial value of accumArray?

Post by David Feuer
The documentation for accumArray is currently broken [*]. According to
According to the documentation,

If the accumulating function is strict, then 'accumArray' is strict in
the values, as well as the indices, in the association list. Thus,
unlike ordinary arrays built with 'array', accumulated arrays should
not in general be recursive.

I believe that purported strictness is desirable, because it prevents
thunks from accumulating when we use the passed function. But the
strictness *isn't really there*. accumArray never forces any values
whatsoever! The same is true of accum, but that function does not
document its strictness.
I propose that we change both the implementation and documentation.
For accumArray, I think we should say that the resulting array is
strict in the initial value and in each result of applying the
accumulating function, and indicate that each element of the resulting
array will be in WHNF.
For accum, I think we should say that the resulting array is strict in
each value in the initial array and in each result of applying the
accumulating function, and indicate that each element of the resulting
array will be in WHNF.
We thereby guarantee that we can accumulate strictly, which is
important for performance, and I think being strict in the initial
value(s) makes for simpler reasoning than only being strict in the
results of the combining function.
[*] https://ghc.haskell.org/trac/ghc/ticket/14785
David Feuer