[Haskell-cafe] Mutable arrays

[Chaddaï Fouché]

2008/2/7, Jeff φ <jeff1.61803 at gmail.com>:
> I played with your foldl1MArray' last night.  I noticed it can be reduced to
> . . .
>
> foldl1MArray' :: (MArray a e m, Ix i) => (e -> e -> e) -> a i e -> m e
> foldl1MArray' f a = do
>      (l,u) <- getBounds a
>     foldl1' (liftM2 f) (map (readArray a) (range (l,u)))
>
> Unfortunately, my new version consumes a lot of stack and heap space.  Why
> is this so inefficient?  Is there a simple change that will make it
> efficient?

This code don't compute the results incrementally, it can't because
foldl1' is not aware of the monad, it only construct a huge action in
m which is then run. foldM advantage is that it can run incrementally.

Which is not to say my code was the best possible (far from it),
already the following would have been better :

> foldlA f a arr = getBounds arr >>=
>                  foldM (\a->a `seq` liftM $ f a) a
>                            . map (readArray arr) . range

> foldl1A f arr = getBounds arr >>= readArray arr . fst >>=
>                 flip (foldlA f) arr

-- 
Jedaï