[Haskell-cafe] vector operations

[Evan Laforge]

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 <jake.mcarthur at gmail.com> wrote:
> Have you already verified that stream fusion won't just do this for you?
>
> On May 23, 2012 12:35 AM, "Evan Laforge" <qdunkan at gmail.com> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe