Tim Pollitt <[EMAIL PROTECTED]> writes:
> The Library Report, (6.1.1) states:
>
> "If the accumulating function is strict, then accumArray is strict in the
> values, as well as the indices, in the association list. ..."
>
> This could lead a naive optimist to hope that a use like
>
> > print $ elems $ accumArray (+) 0 (0,0) (replicate 1000000 (0,1))
>
> would display "[1000000]", needing little stack and heap. I can't imagine
> accumArray (or arrays in general) being of much use in 'real' applications
> if such behaviour isn't somehow attainable.
>
> 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. Perhaps we need a strict
version of accumArray.
Cheers,
Simon
--
Simon Marlow [EMAIL PROTECTED]
University of Glasgow http://www.dcs.gla.ac.uk/~simonm/
finger for PGP public key
