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] Re: Comparing data structures which contain functions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-06-03 (02:30)
From: Jon Harrop <jdh30@c...>
Subject: [Caml-list] Re: Comparing data structures which contain functions

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?


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

 an application I failed to analyze using the 
heapstats tool.

-- Christian 

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

From  Thu Jun  3 09:50:37 2004
Received: (from majordomo@localhost) by (8.7.6/8.7.3) id JAA02892; Thu, 3 Jun 2004 09:50:37 +0200 (MET DST)
X-Authentication-Warning: majordomo set sender to using -f
Received: from ( []) by (8.7.6/8.7.3) with ESMTP id JAA08775 for <>; Thu, 3 Jun 2004 09:42:45 +0200 (MET DST)
Received: from ( [])
	by (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 [])
          by (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 <>
Subject: Re: [Caml-list] Teaching OCaml
In-Reply-To: <>
References: <>
X-Mailer: VM 7.03 under Emacs 20.7.2
Reply-To: (Jean-Christophe Filliatre)
X-MailScanner: Found to be clean
X-Miltered: at concorde with ID 40BED674.002 by Joe's j-chkmail (!
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 
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.


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