From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA00755; Sat, 3 May 2003 10:17:03 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA31644 for ; Sat, 3 May 2003 10:17:01 +0200 (MET DST) Received: from mail.exomi.com (mail.exomi.com [217.169.64.72]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h438H0H18059 for ; Sat, 3 May 2003 10:17:00 +0200 (MET DST) Received: from exomi.com (unknown [10.0.5.5]) by mail.exomi.com (Postfix) with ESMTP id 6FC1A5E73; Sat, 3 May 2003 11:16:59 +0300 (EEST) Date: Sat, 3 May 2003 11:16:58 +0300 Subject: Re: [Caml-list] Efficiency of 'a list Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v552) Cc: , "'Ocaml Mailing List'" To: "Mattias Waldau" From: Ville-Pertti Keinonen In-Reply-To: <03b801c31136$e122db50$0200a8c0@gateway> Message-Id: <9BE14E24-7D3F-11D7-BCFA-000393863F70@exomi.com> Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.552) X-Spam: no; 0.00; caml-list:01 resonable:01 hashes:01 high-level:01 datatypes:01 dynamically:01 statically:01 compile-time:01 consing:01 deconstruct:01 generics:01 scalable:01 arrays:01 inconsistent:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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