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

[Gregory Crosswhite]

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