
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.
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.
On Wed, May 23, 2012 at 5:13 AM, Jake McArthur
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