[Haskell-cafe] What's the deal with Clean?
gcross at phys.washington.edu
Tue Nov 3 22:07:26 EST 2009
Actually, it's not a typo. If you look at the source, what you'll see
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
| otherwise = loop_index n0 s0
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.
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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe