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