Re: [Caml-list] Efficiency of 'a list

[Ville-Pertti Keinonen <will@exomi.com>]

> Many modern programming languages (JavaScript, Perl, PHP) have arrays
> that can take arbitrary keys as an index. This makes many people use
> them all the time, and it makes the programs resonable efficient, since
> people do not loop all the time.

They aren't arrays, you most likely mean maps aka hashes aka 
associative arrays, which are an entirely different type.

> I think more conventional languages like Java and Ocaml could learn 
> from
> this and introduce more advanced data structures as primitives, for
> example replace lists by sets, and let arrays take arbitrary data types

One big difference here is that the languages providing high-level 
primitive datatypes are much higher level languages, and they are 
dynamically typed.  They need higher level primitive types because you 
can't define your own types efficiently enough.

Java and OCaml are statically typed, which has significant advantages 
in terms of performance and compile-time verification (although Java 
throws away much of that advantage by designing part of the language as 
if it were dynamically typed, forcing you to widen and narrow types for 
storage - the worst of both worlds, in many respects).

Giving up lists or arrays is a very bad idea.  An array has 
constant-time lookup, unlike a map.  A list can be constructed in O(n) 
time (by consing up), unlike a set.  Neither is an appropriate data 
type to use for a collection from which you want to frequently search 
based on a key, but they are useful and efficient when used correctly.

Primitive 'a set and ('a, 'b) map types in OCaml would certainly be 
possible, but as far as I can tell, the only advantages a primitive 
type would have over a library type would be the ability to construct 
an instance literally (construction is already easy using 
List/Array.fold_left over a list/array of items or tuples) and to 
deconstruct using pattern matching (whatever that would even mean - in 
any case, it would be inconsistent with what pattern matching currently 
does).

In Java, primitive sets and maps would perhaps have a bit more of an 
advantage, since currently library types are significantly weaker than 
primitive types (primitive arrays are the only parametrized type in 
Java).  But I think introducing more primitive types is the wrong 
solution (it would only make the Java type system even more 
inconsistent than it already is).  The right solution is to fix the 
language to make library types more powerful.  Introducing generics is 
one way to do this, and apparently what is being done.

> as index. This would automatically improve the O-behavior of the
> programs, ie. make them more scalable.

No, it would only improve the behavior of poorly written programs, and 
it would make make some programs perform worse.

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