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] Efficiency of 'a list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-05-04 (02:08)
From: cashin@c...
Subject: Re: [Caml-list] Efficiency of 'a list
"Mattias Waldau" <> writes:

> *** Do not use lists, there is always a better datastructure *** 

That's kind of silly.  Sometimes lists are the natural datastructure
to use.  If you know what you're doing, use lists when appropriate!

I suppose the reason nobody else has responded to this
over-generalization is that it's really not specific to ocaml and so
of questionable relevance here.  However, I don't like thinking that
people who aren't yet comfortable with data structures may be reading
this suggestion and taking it literally.

Whenever you've got a situation where access is always via
straightforward iteration and modification is at the beginning or end
of a sequence, it doesn't make sense to use a hash table or even a
tree.  When you don't know the size ahead of time, it doesn't make
sense to use an array either.  A list is just the right thing in that

Witness the linux kernel, which uses lists when lists are the most
natrural, efficient data structure for the task at hand.  

> The result of this is that you get all these questions in this forum
> complaining about performance. Most of the questions would never
> have been asked if the author would have used the correct
> datastructure, mostly Hash/Map or Set.

The solution is not to compound the confusion by saying, "don't use
lists".  It would be more helpful to point to resources that describe
what data structures to use under different circumstances.

--Ed L Cashin     PGP public key:

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