[Haskell-cafe] What's the deal with Clean?

Don Stewart 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.

-- 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe


More information about the Haskell-Cafe mailing list