[Haskell-cafe] Data.Foldable UArray
Marcus D. Gabriel
marcus at gabriel.name
Sun Feb 23 09:52:16 UTC 2014
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.
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 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.
>  https://github.com/haskell/bytestring/pull/9
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe