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

- Greg


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

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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to