[Haskell-cafe] vector operations

Evan Laforge qdunkan at gmail.com
Wed May 23 06:33:36 CEST 2012


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?



More information about the Haskell-Cafe mailing list