From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6995sj6013414
	for <caml-list@sympa-roc.inria.fr>; Sat, 9 Jul 2011 11:05:54 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Au8CAGwZGE7Unwdkimdsb2JhbABUmF+OchQBAQEKCQ0HEgYhiHzBWYY6BJdSi0o
X-IronPort-AV: E=Sophos;i="4.65,503,1304287200"; 
   d="scan'208";a="86875325"
Received: from relay.pcl-ipout02.plus.net ([212.159.7.100])
  by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 09 Jul 2011 11:05:50 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AigHAJIZGE5UXeb0/2dsb2JhbABUmF+OcneIfMFahjoEl1KLSg
Received: from outmx03.plus.net ([84.93.230.244])
  by relay.pcl-ipout02.plus.net with ESMTP; 09 Jul 2011 10:05:49 +0100
Received: from [87.112.222.234] (helo=WinEight)
	 by outmx03.plus.net with esmtp (Exim) id 1QfTTx-00058C-1O
	for caml-list@inria.fr; Sat, 09 Jul 2011 10:05:49 +0100
From: "Jon Harrop" <jon@ffconsultancy.com>
To: <caml-list@inria.fr>
References: <4E0CAEC3.7010804@gmail.com>
In-Reply-To: <4E0CAEC3.7010804@gmail.com>
Date: Sat, 9 Jul 2011 10:05:34 +0100
Message-ID: <028c01cc3e17$5d3d4c50$17b7e4f0$@ffconsultancy.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQI8G6UJXRbPZwVwzVnBSXz6cYYvF5QD9shw
Content-Language: en-gb
Subject: RE: [Caml-list] Priority queues, reloaded

Andrew wrote:
> Since the previous discussion regarding priority queues pretty much
concluded
> that they weren't available in OCaml, could you point to the most compact
> implementation that you know of? I'm very likely to have to recode my own
> implementation in a time-restricted setting, so I'd love to hear about
efficient-
> yet-easy/fast-to-implement options.

Skew heap from Okasaki translated to OCaml:

    module SkewHeap(Elt: Set.OrderedType) = struct
      type t = E | T of Elt.t * t * t

      let empty = E
        
      let is_empty = function E -> true | _ -> false
      
      let rec merge t1 t2 =
        match t1, t2 with
        | E, t | t, E -> t
        | T(x, l1, r1), T(y, l2, r2) ->
            let c = Elt.compare x y in
            if c<=0 then T(x, merge t2 r1, l1) else T(y, merge t1 r2, l2)
       
      let insert x h = merge (T(x, E, E)) h
        
      let min = function
        | E -> None
        | T(x, l, r) -> Some(x, merge l r)
    end;;

Cheers,
Jon.