On Fri, 24 Aug 2001, Lars Nilsson wrote:
>At the risk of making a fool of myself in public, is there such a thing as
>insertion in a list at all in Ocaml? From what I have seen there is only
>concatenation of a single element and a list (::), and operations would have
>to be defined with this by means recursion/iteration. If this is the case, I
>assume insertion at some point in a list would have O(n) complexity in the
>general case? If not, what am I missing (@ being something other than I
>think?)

You are right, only :: is possible. So insertion at arbitrary positions is O(n)
time.

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr