[Haskell-cafe] Data.Foldable UArray

[Michael Snoyman]

On Sat, Feb 22, 2014 at 10:17 PM, Tom Ellis <
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/f3eb5063/attachment.html>