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 RAA12465; Wed, 25 Sep 2002 17:39:22 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA12461 for ; Wed, 25 Sep 2002 17:39:20 +0200 (MET DST) Received: from web11205.mail.yahoo.com (web11205.mail.yahoo.com [216.136.131.187]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id g8PFdJ529164 for ; Wed, 25 Sep 2002 17:39:19 +0200 (MET DST) Message-ID: <20020925153918.52238.qmail@web11205.mail.yahoo.com> Received: from [195.224.189.78] by web11205.mail.yahoo.com via HTTP; Wed, 25 Sep 2002 08:39:18 PDT Date: Wed, 25 Sep 2002 08:39:18 -0700 (PDT) From: Noel Welsh Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive? To: Brian Hurt Cc: caml-list In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk O'Caml's heritage is from the functional world, so side-effects are discouraged. Maintaining a tail pointer requires side-effects. For more insight consider that a list is defined by its recursive definition: List 'a := Cons 'a * List | Null A list is a cons cell containing an element and the rest of the list, or null, which terminates the list. Now tell me which cons cell is the head, and so should maintain the tail pointer. Welcome to a world of pain! HTH, Noel __________________________________________________ Do you Yahoo!? New DSL Internet Access from SBC & Yahoo! http://sbc.yahoo.com ------------------- 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