[Haskell-cafe] What's the deal with Clean?
dons at galois.com
Wed Nov 4 00:15:11 EST 2009
Well, it depends on which indexU the OP means. The one linked in the docs is
the O(1) UA type class version.
> 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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe