Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-09-25 (15:42)
From: Oleg <oleg_inconnu@m...>
Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
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.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: