Version française
Home     About     Download     Resources     Contact us    
Browse thread
Data structure efficiency questions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Stefan Monnier <monnier+lists/caml/news/@R...>
Subject: Re: Data structure efficiency questions
>>>>> "Jean-Christophe" == Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> 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