Re: [Caml-list] Reading a large text file

[Richard Jones <rich@annexia.org>]

On Sat, May 01, 2004 at 11:43:51AM -0400, Rahul Siddharthan wrote:
> Brian Hurt said on May  1, 2004 at 09:03:56:
> > But what I'm guessing is happening is that you are appending (adding to 
> > the end of) your list, and that this is what is killing you.  To add an 
> > element to the *end* of a list, Ocaml has to completely reallocate the 
> > entire list- turning what you might think is an O(1) operation into an 
> > O(n) operation.
> 
> I'm pretty puzzled by that: why would it have to do that?  Arrays,
> yes, but lists, can't it just traverse the existing list to its end
> and then add a new element?  It's still O(n) but no reallocation.

The short answer is no, because in OCaml (unlike in LISP) lists are
immutable.  In LISP terminology, there's no way to 'set cdr' on an
OCaml 'cons structure'.  The disadvantage to this is that you can't do
certain destructive operations on lists, like you can so easily in
LISP.  The advantage is that you can't do certain destructive
operations on lists!  In other words, your code is more likely to be
bug free.

However, OCaml is a practical language and so allows you to create a
mutable cons structure if you so desire.  eg:

# type 'a mylist = { head : 'a; mutable tail : 'a mylist option };;
type 'a mylist = { head : 'a; mutable tail : 'a mylist option; }

# let xs = { head = 10; tail = None };;
val xs : int mylist = {head = 10; tail = None}
# let xs = { head = 5; tail = Some xs};;
val xs : int mylist = {head = 5; tail = Some {head = 10; tail = None}}

# let ys = { head = 20; tail = None };;		(* new tail *)
val ys : int mylist = {head = 20; tail = None}

# xs.tail <- Some ys;;				(* replace tail of xs *)
- : unit = ()
# xs;;
- : int mylist = {head = 5; tail = Some {head = 20; tail = None}}

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MAKE+ is a sane replacement for GNU autoconf/automake. One script compiles,
RPMs, pkgs etc. Linux, BSD, Solaris. http://www.annexia.org/freeware/makeplus/

-------------------
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