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
