Re: [Haskell-cafe] vector operations

On 29/05/2012, at 19:49, Evan Laforge wrote:

Good question.. I copied both to a file and tried ghc-core, but it inlines big chunks of Data.Vector and I can't read it very well, but it looks like the answer is no, it still builds the the list of sums. I guess the next step is to benchmark and see how busy the gc is on each version.

Vector should definitely fuse this, if it doesn't it's a bug. Please report if it doesn't for you. To verify, just count the number of letrecs in the optimised Core. You'll see one letrec if it has been fused and two if it hasn't.

But my impression was that stream fusion can't handle early aborts, which was why I was wondering why Vector lacks a foldAbort type function.

Stream fusion easily handles early aborts. There isn't anything like foldAbort precisely because it can be built out of existing operations at no extra cost. Roman

On Wed, May 23, 2012 at 5:13 AM, Jake McArthur wrote:

...

Have you already verified that stream fusion won't just do this for you?

On May 23, 2012 12:35 AM, "Evan Laforge" wrote:

...

So I wanted to find the first index in a vector whose running sum is greater than a given number.

The straightforward way is to create the running sum and then search:

Vector.findIndex (>=target) (Vector.scanl' (+) 0 vector)

But vectors are strict so it could do extra work, and what if I don't want to generate garbage? I could do it with a fold, but it would have to have the ability to abort early. Of course I could write such a fold myself using indexing:

import qualified Data.Vector.Generic as Vector

fold_abort :: (Vector.Vector v a) => (accum -> a -> Maybe accum) -> accum -> v a -> accum fold_abort f accum vec = go 0 accum where go i accum = maybe accum (go (i+1)) $ f accum =<< vec Vector.!? i

find_before :: (Vector.Vector v a, Num a, Ord a) => a -> v a -> Int find_before n = fst . fold_abort go (0, 0) where go (i, total) a | total + a >= n = Nothing | otherwise = Just (i+1, total+a)

So it's bigger and clunkier, but I would think it would be much more efficient (provided using Data.Vector.Generic won't inhibit inlining and unboxing). But I'm a bit surprised there isn't already something like fold_abort... or is there?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe