[Haskell-cafe] vector operations

[Roman Leshchinskiy]

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 <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
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe