What is the amortized time complexity of Haskell’s `!?` operator?

  Kiến thức lập trình

The documentation says:

List index (subscript) operator, starting from 0. Returns Nothing if the index is out of bounds
This is the total variant of the partial !! operator.
WARNING: This function takes linear time in the index.

However a timing suggests otherwise, perhaps because of the way GHC only computes expressions once per evaluation of the outer context?

ghci> length $ map ([0..10^8-1] !?) . map (`mod` (10^8 - 1)) $ [0..1 * 10^8 - 1]
100000000
(1.16 secs, 24,800,308,224 bytes)
ghci> length $ map ([0..10^8-1] !?) . map (`mod` (10^8 - 1)) $ [0..4 * 10^8 - 1]
400000000
(4.55 secs, 99,200,308,200 bytes)

Does anyone know of an authoritative reference to figure this out?

LEAVE A COMMENT