[Haskell-cafe] Data.Foldable UArray

[Marcus D. Gabriel]

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 at jaguarpaw.co.uk <mailto:tom-lists-haskell-cafe-2013 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140223/9a2237ed/attachment.html>