My intuition is that Tom is correct in his supposition.

> -- Performance comparaisons
> arrayFoldl' :: (Ix i, IArray a e) => (t -> e -> t) -> t -> a i e -> t
> arrayFoldl' f z = L.foldl' f z . elems
>
> arrayFold :: (Enum i, Ix i, IArray a e) => (t -> e -> t) -> t -> a i e -> t
> arrayFold f z a =
>   let (lo, hi) = bounds a
>       arrayFold_ i z' =
>         if i <= hi
>         then arrayFold_ (succ i) (f z' (a!i) )
>         else z'
>   in arrayFold_ lo z

If you are willing to accept the (Enum i), then I did not observe any
differences in space and time performance between the two functions
above with the '-O2' option and using UArray.  Note I used the word
experience, not test.

- Marcus

On 23/02/2014 05:56, Michael Snoyman wrote:



On Sat, Feb 22, 2014 at 10:17 PM, Tom Ellis <tom-lists-haskell-cafe-2013@jaguarpaw.co.uk> wrote:
On Sat, Feb 22, 2014 at 07:15:22PM +0000, Dominic Steinitz wrote:
> > Since all 'Foldable' functions factor through 'toList', you can't go too
> > wrong by using '(foldableFunction . toList) myArray' wherever you would have
> > wanted to use 'foldableFunction myArray'.
>
> Isn't this going to be rather inefficient? Presumably the point of
> using an array is to avoid using lists for an application where they
> are not appropriate?

(I'll take this opportunity to correct myself: I meant 'foldableFunction .
elems', not 'foldableFunction . toList')

Marcus's proposed Foldable instance used 'elems' anyway, and furthermore the
public API to UArray (which is just IArray) provides no other suitable means
of folding the elements, so there's hardly something "more efficient" to
compare to.

It would be interesting to see if a more efficient implementation of 'foldr'
and friends could be written using the internal interface, but I wouldn't be
terribly surprised if it were no better that the naive approach plus list
fusion.  (I'm far from expert though).


It's not exactly the same thing, but I recently sent a pull request for a more efficient version of mapM_ in bytestring[1] which avoids an intermediate list representation. This implementation is already used in both mono-traversable's omapM_ and Data.Conduit.Binary.mapM_, and I've seen significant performance gain by using it. I'd imagine the same would be true for UArray. At the very least, I'd try using explicit array indexing instead of converting to a list and see how that affects performance.

[1] https://github.com/haskell/bytestring/pull/9