Simon Marlow wrote:
>
> Tim Pollitt <[EMAIL PROTECTED]> writes:
>
> > "If the accumulating function is strict, then accumArray is strict in the
> > values, as well as the indices, in the association list. ..."
...
> > In fact, both stack and heap reqirements seem to be linear in the size of the
> > association list.
> >
> > I notice the definition in PrelArr.lhs uses foldr over the list, so from that
> > alone I'd expect problems, but I'm sure there's much more to it.
>
> I didn't look into it in great detail, but it looks to be a
> combination of the use of foldr and the call
>
> writeArray arr i (f old_v new_v)
>
> in zap_with_f. This just updates the array entry with a new thunk
> which refers to the old thunk, so any use of this function will by
> definition require linear heap space. ...
Thanks for the quick response. You're right about the accumulation of
thunks. I was wrong to suspect foldr; it's threading the array updates
so it's exactly the form of fold it should be.
> ... Perhaps we need a strict
> version of accumArray.
Yes please. There are also occasions when a strict version of array
would be beneficial. Eg.: building a large lookup table as an array
where associations are independent, or ordered with no forward
dependencies. The initialising thunks can require many times the space
needed for the reduced values, and the big peak in heap usage can cause
horrible thrashing in a program which would otherwise run comfortably in
much less memory.
TWP
