[Haskell-cafe] What's the deal with Clean?
gcross at phys.washington.edu
Wed Nov 4 00:22:26 EST 2009
Oh, that's strange... the type class "UA" is defined twice, once in
Data.Array.Vector and once in Data.Array.Vector.UArr; in the first
module indexU is a separate function with the sources I exhibited, in
the second module it is a method of the UA type-class which seems to
have O(1) access for most of the defined instances.
That's incredibly confusing...
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
>> Actually, it's not a typo. If you look at the source, what you'll
>> 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
>> 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