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 RAA12561; Wed, 25 Sep 2002 17:42:05 +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 RAA12557 for <caml-list@pauillac.inria.fr>; Wed, 25 Sep 2002 17:42:04 +0200 (MET DST)
Received: from dewberry.cc.columbia.edu (dewberry.cc.columbia.edu [128.59.59.68])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g8PFg3D20444
	for <caml-list@inria.fr>; Wed, 25 Sep 2002 17:42:03 +0200 (MET DST)
Received: from there (tw304h3.cpmc.columbia.edu [156.111.84.180])
	by dewberry.cc.columbia.edu (8.9.3/8.9.3) with SMTP id LAA26761;
	Wed, 25 Sep 2002 11:41:47 -0400 (EDT)
Message-Id: <200209251541.LAA26761@dewberry.cc.columbia.edu>
Content-Type: text/plain;
  charset="iso-8859-1"
From: Oleg <oleg_inconnu@myrealbox.com>
To: Brian Hurt <brian.hurt@qlogic.com>,
        Ocaml Mailing List <caml-list@inria.fr>
Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
Date: Wed, 25 Sep 2002 11:42:08 -0400
X-Mailer: KMail [version 1.3.2]
References: <Pine.LNX.4.33.0209250958520.1974-100000@eagle.ancor.com>
In-Reply-To: <Pine.LNX.4.33.0209250958520.1974-100000@eagle.ancor.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

On Wednesday 25 September 2002 11:33 am, Brian Hurt wrote:
> I get that the cost of list concatenation is proportional to the length of
> the first list.  So (elem :: list) is O(1) no matter what the length of
> list is.  But (list :: elem) is O(n), with n being the length of the list.
>
> Why doesn't Ocaml keep a pointer to the last element of the list, as well
> as the first element?  This would make all list concatenation (in
> situations where you don't have to duplicate a list) an O(1) operation.  
> At the cost of increasing the size of a list object.

let a = [1; 2; 3; 4; 5; 6];;
let b = 0 :: a;;

the elements of "a" are _shared_. Now your suggestion regarding "efficient 
append" can not be used to append anything to one list, but not the other.

HTH
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners