From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA31718; Fri, 24 Aug 2001 14:28:09 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA31678 for ; Fri, 24 Aug 2001 14:28:08 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f7OCS7n21632 for ; Fri, 24 Aug 2001 14:28:07 +0200 (MET DST) Received: from (filliatr@localhost) by lri.lri.fr (8.11.1/jtpda-5.3.2) id f7OCRnV01855 ; Fri, 24 Aug 2001 14:27:49 +0200 (MEST) From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15238.18501.528683.170652@lri> Date: Fri, 24 Aug 2001 14:27:49 +0200 (MEST) To: "Lars Nilsson" Cc: Subject: Re: [Caml-list] time complexity on basic data types In-Reply-To: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> References: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> X-Mailer: VM 6.49 under Emacs 20.7.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Lars Nilsson writes: > 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're right. But a list is not the adequate data structure if you want to insert at some arbitrary points in it. It is a stack-like data structure (i.e. push and pop are O(1)) or can be used when you want to aggregate elements regardless the order and then iterate over / traverse all of them. If you really want to insert at any point in O(1), you may consider using mutable linked lists (see for instance the implementation of the module Queue in ocaml standard library). You loose persistence, but it may not be mandatory in your case. Hope this helps, -- Jean-Christophe Filliatre mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr ------------------- 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