[Haskell] Re: Looking for a random-access sequence data structure

[Duncan Coutts]

On Fri, 2006-01-13 at 15:21 +0100, Christian Maeder wrote:
> Duncan Coutts wrote:
> >> What's the semantics of insert? Does it replace an element, or does it
> >> shirt all the elements after it one step?
> > 
> > It shifts all the elements after it one step. So that's why all the
> > finite map types are no help.
> 
> import Data.Map as Map
> 
> seqInsert i v = Map.insert i v
>    . Map.mapKeysMonotonic (\ j -> if j < i then j else j + 1)

Ah, ok so it can be done, but it's linear rather than log time.

Duncan