From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA30817 for caml-red; Wed, 20 Sep 2000 21:50:38 +0200 (MET DST) 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 VAA26443 for ; Tue, 19 Sep 2000 21:07:30 +0200 (MET DST) Received: from tequila.cs.yale.edu (tequila.cs.yale.edu [128.36.229.152]) by nez-perce.inria.fr (8.10.0/8.10.0) with ESMTP id e8JJ7TT16841 for ; Tue, 19 Sep 2000 21:07:29 +0200 (MET DST) Received: from tequila.cs.yale.edu (localhost [127.0.0.1]) by tequila.cs.yale.edu (8.9.3/8.9.3) with SMTP id PAA31361 for ; Tue, 19 Sep 2000 15:07:24 -0400 To: caml-list@inria.fr From: "Stefan Monnier" Newsgroups: lists.caml Subject: Re: Data structure efficiency questions References: <14791.6318.709323.906054@pc803> User-Agent: Gnus/5.0804 (Gnus v5.8.4) Emacs/21.0.90 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Path: rum.cs.yale.edu NNTP-Posting-Host: rum.cs.yale.edu Message-ID: <39c7b967@tequila.cs.yale.edu> Date: 19 Sep 2000 15:07:19 -0500 X-Trace: 19 Sep 2000 15:07:19 -0500, rum.cs.yale.edu Sender: weis@pauillac.inria.fr >>>>> "Jean-Christophe" == Jean-Christophe Filliatre writes: > In his message of September 18, 2000, David=?iso-8859-1?Q?_Mentr=E9?= writes: >> 1. Is the @ operator costly or is it implemented as a simple pointers >> manipulation? I'm not sure what you mean by "not costly" since the "pointer manipulation" still requires to go down one of the lists. > @ cannot be implemented as a simple pointer manipulation, because > lists are persistent data structures. It means that l1 and l2 must > remain the same lists after the evaluation of l1 @ l2. You could of course have a list datatype as (pardon the SML syntax): datatype 'a list = Nil | Cons of 'a * 'a list | @ of 'a list * 'a list Although this probably wouldn't be described as "pointer manipulation". Stefan