Proposal: accum and accumArray strictness

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: accum and accumArray strictness

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?

On Fri, Feb 9, 2018 at 3:52 PM, David Feuer <[hidden email]> wrote:

> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries