UArr operations subject to stream fusion: http://code.haskell.org/~dons/code/uvector/Data/Array/Vector/Strict/
Direct-style operations, not subject to the optimization: http://code.haskell.org/~dons/code/uvector/Data/Array/Vector/UArr.hs /me needs to write a tutorial on this. -- Don briand: > Don, > > There is more than one indexU ? > > In Data.Array.Vector there is only 1 indexU that I can find. > > Brian > > On Nov 3, 2009, at 9:15 PM, Don Stewart wrote: > >> Well, it depends on which indexU the OP means. The one linked in the >> docs is >> the O(1) UA type class version. >> >> -- Don >> >> gcross: >>> Actually, it's not a typo. If you look at the source, what you'll >>> see >>> is >>> >>> indexU arr n = indexS (streamU arr) n >>> >>> and then tracking down indexS, you'll see >>> >>> >>> indexS (Stream next s0 _) n0 >>> | n0 < 0 = error "Data.Array.Vector.Stream.indexS: negative >>> index" >>> | otherwise = loop_index n0 s0 >>> where >>> loop_index n s = case next s of >>> Yield x s' | n == 0 -> x >>> | otherwise -> s' `seq` loop_index (n-1) s' >>> Skip s' -> s' `seq` loop_index n s' >>> Done -> error >>> "Data.Array.Vector.Stream.indexS: >>> index too large" >>> >>> >>> So in other words, indexU really does have O(n) complexity since it >>> first converts the array into a stream and then walks down the >>> stream in >>> order to find the desired element. >>> >>> Cheers, >>> Greg >>> >>> >>> On Nov 3, 2009, at 6:25 PM, Roman Leshchinskiy wrote: >>> >>>> On 04/11/2009, at 13:12, brian wrote: >>>> >>>>> indexU :: UA e => UArr e -> Int -> e >>>>> >>>>> O(n). indexU extracts an element out of an immutable unboxed array. >>>> >>>> This is a typo (unless Don inserted a nop loop into the original DPH >>>> code). >>>> >>>> Roman >>>> >>>> >>>> _______________________________________________ >>>> 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 >> _______________________________________________ >> 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