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 EAA30977; Thu, 3 Jun 2004 04:30:15 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id EAA00394 for ; Thu, 3 Jun 2004 04:30:13 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i532UAEV003854 for ; Thu, 3 Jun 2004 04:30:13 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1BVhze-0007e1-D8 for caml-list@inria.fr; Thu, 03 Jun 2004 02:30:10 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@inria.fr Subject: [Caml-list] Re: Comparing data structures which contain functions Date: Thu, 3 Jun 2004 03:28:47 +0100 User-Agent: KMail/1.6.2 MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200406030328.47160.jdh30@cam.ac.uk> Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 40BE8D32.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ignoring:01 exception:02 argument:03 data:03 data:03 wondering:04 functions:05 functions:05 structures:05 structures:05 cheers:06 comparing:09 raised:10 values:11 causes:11 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk I believe that any attempt to compare data structures which contain functions which results in an attempt to compare values which are functions causes the "Invalid_argument" exception to be raised. I was just wondering if it is easy to compare data structures on everything else, ignoring any functions in them? Cheers, Jon. ------------------- 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 an application I failed to analyze using the heapstats tool. -- Christian ------------------- 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 From owner-caml-list@pauillac.inria.fr Thu Jun 3 09:50:37 2004 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA02892; Thu, 3 Jun 2004 09:50:37 +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 JAA08775 for ; Thu, 3 Jun 2004 09:42:45 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i537giSH014228 for ; Thu, 3 Jun 2004 09:42:45 +0200 Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id i537aJCr020644 ; Thu, 3 Jun 2004 09:36:19 +0200 (MEST) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1BVmlv-00058c-00; Thu, 03 Jun 2004 09:36:19 +0200 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16574.54515.560699.848619@gargle.gargle.HOWL> Date: Thu, 3 Jun 2004 09:36:19 +0200 To: Holger Schulz Cc: caml-list@inria.fr Subject: Re: [Caml-list] Teaching OCaml In-Reply-To: <03CA2ED3-B4BC-11D8-86A1-000A95C6FE96@mathematik.uni-siegen.de> References: <40A8A1F6.3090604@di.ubi.pt> <69392398-A827-11D8-89DA-0003939A19AA@fas.harvard.edu> <20040518085224.GA15477@redhat.com> <03CA2ED3-B4BC-11D8-86A1-000A95C6FE96@mathematik.uni-siegen.de> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Miltered: at concorde with ID 40BED674.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 caml-list:01 quicksort:01 haskell:01 heapsort:01 worst-case:01 heapsort:01 ocaml's:01 quicksort:01 arrays:01 arrays:01 ocaml:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > >> Iif you want practical features of OCaml, you could try the classic > >> "QuickSort in n lines" where n depends on how efficient you want to > >> make it, but you can still achieve O(n log n) in something like 4 > >> lines. It takes 10 or so to be efficient, compared to at least 50 in > >> C. Of course, Haskell has even nicer syntax for this, but it looks > >> good in O'Caml too. I don't think sorting is a good example of ocaml power w.r.t other languages. If you are sorting arrays, an ocaml code and a C code won't differ so much and I don't see why the C code would be 10 times longer (the C syntax could even make it smaller). If you are sorting lists, I agree that ocaml syntax and pattern matching would make the code much concise than the C equivalent. > By the way: are the 4 or 10 line source available online anywhere? I'd > like to take a look at. Achieving O(n log n) in 4 lines and an efficient implementation in 10 lines is probably underestimated (again on arrays, not lists) but here is a 10 lines implementation of in-place heapsort, which has O(n log n) worst-case complexity: ====================================================================== let swap a i j = let t = a.(i) in a.(i) <- a.(j); a.(j) <- t let rec downheap a k n = let j = 2 * k+1 in if j <= n then let j' = if j+1 <= n then if a.(j) < a.(j+1) then j+1 else j else j in if a.(k) < a.(j') then begin swap a k j'; downheap a j' n end let heapsort a = let n = Array.length a in for k = (n-2) / 2 downto 0 do downheap a k (n-1) done; for k = n-1 downto 1 do swap a 0 k; downheap a 0 (k-1) done ====================================================================== (This code has been proved correct formally.) The Array.sort from ocaml's standard library is also an implementation of in-place heapsort, but it is much more optimized than this one. It is also possible to write quicksort on arrays in 10 lines (using Bentley's trick for partitioning) but the complexity is not exactly the same, as everybody knows. Note: I don't intend to start a flame on how to write sorting algorithms (I'm not at all a specialist); I just wanted to answer Holger's question. -- Jean-Christophe ------------------- 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