Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
From: Noel Welsh <noelwelsh@y...>
Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
O'Caml's heritage is from the functional world, so
side-effects are discouraged.  Maintaining a tail
pointer requires side-effects.  

For more insight consider that a list is defined by
its recursive definition:

List 'a :=  Cons 'a * List
        |   Null

A list is a cons cell containing an element and the
rest of the list, or null, which terminates the list. 
Now tell me which cons cell is the head, and so should
maintain the tail pointer. Welcome to a world of pain!

HTH,
Noel


__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com
-------------------
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