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 p6992na2013170
	for <caml-list@sympa-roc.inria.fr>; Sat, 9 Jul 2011 11:02:49 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Aq4CADIYGE7Unwdjk2dsb2JhbABUp1EUAQEBAQkJCwkUBCGIfMFghjoEhx+QM4tK
X-IronPort-AV: E=Sophos;i="4.65,503,1304287200"; 
   d="scan'208";a="86875130"
Received: from relay.pcl-ipout01.plus.net ([212.159.7.99])
  by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 09 Jul 2011 11:02:43 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EADIYGE5UXeb0/2dsb2JhbABUp1F3iHzBYIY6BIcfkDOLSg
Received: from outmx03.plus.net ([84.93.230.244])
  by relay.pcl-ipout01.plus.net with ESMTP; 09 Jul 2011 10:02:42 +0100
Received: from [87.112.222.234] (helo=WinEight)
	 by outmx03.plus.net with esmtp (Exim) id 1QfTQw-0004g9-Ed; Sat, 09 Jul 2011 10:02:42 +0100
From: "Jon Harrop" <jon@ffconsultancy.com>
To: "=?iso-8859-1?Q?'Jean-Christophe_Filli=E2tre'?=" <Jean-Christophe.Filliatre@lri.fr>,
        "Caml List" <caml-list@inria.fr>
References: <4E0CAEC3.7010804@gmail.com> <BANLkTinAfZGdJ19mRjpoqVTvN9dpCNymFw@mail.gmail.com> <4E0CC220.8010706@lri.fr>
In-Reply-To: <4E0CC220.8010706@lri.fr>
Date: Sat, 9 Jul 2011 10:02:27 +0100
Message-ID: <028b01cc3e16$ee050210$ca0f0630$@ffconsultancy.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQI8G6UJXRbPZwVwzVnBSXz6cYYvFwHoRqBkAdc6MDST4e3ssA==
Content-Language: en-gb
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p6992na2013170
Subject: RE: [Caml-list] Priority queues, reloaded

Jean-Christophe Filliātre wrote:
> Wow, that's impressive! But I guess you didn't need to implement the
remove
> operation on red-black trees :-) That's a real pain.

Is Kahrs' so bad:

delete :: Ord a => a -> RB a -> RB a
delete x t =
	case del t of {T _ a y b -> T B a y b; _ -> E}
	where
	del E = E
	del (T _ a y b)
	    | x<y = delformLeft a y b
	    | x>y = delformRight a y b
            | otherwise = app a b
	delformLeft a@(T B _ _ _) y b = balleft (del a) y b
	delformLeft a y b = T R (del a) y b
	delformRight a y b@(T B _ _ _) = balright a y (del b)
	delformRight a y b = T R a y (del b)

balleft :: RB a -> a -> RB a -> RB a
balleft (T R a x b) y c = T R (T B a x b) y c
balleft bl x (T B a y b) = balance bl x (T R a y b)
balleft bl x (T R (T B a y b) z c) = T R (T B bl x a) y (balance b z (sub1
c))

balright :: RB a -> a -> RB a -> RB a
balright a x (T R b y c) = T R a x (T B b y c)
balright (T B a x b) y bl = balance (T R a x b) y bl
balright (T R a x (T B b y c)) z bl = T R (balance (sub1 a) x b) y (T B c z
bl)

sub1 :: RB a -> RB a
sub1 (T B a x b) = T R a x b
sub1 _ = error "invariance violation"

From:

  http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.hs

Anyone got this in OCaml?

Cheers,
Jon.