Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Oleg <oleg_inconnu@myrealbox.com>]

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