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
