From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 29E86BC0B for ; Tue, 16 Jan 2007 09:32:25 +0100 (CET) Received: from dorado.vub.ac.be (smtp.vub.ac.be [134.184.129.10]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0G8WObe017645 for ; Tue, 16 Jan 2007 09:32:24 +0100 Received: from exchange.etro.vub.ac.be (etro10.vub.ac.be [134.184.2.10]) by dorado.vub.ac.be (Postfix) with ESMTP id 58AB253C for ; Tue, 16 Jan 2007 09:32:24 +0100 (CET) Received: from ssel.vub.ac.be ([10.0.4.37]) by exchange.etro.vub.ac.be with Microsoft SMTPSVC(6.0.3790.1830); Tue, 16 Jan 2007 09:32:24 +0100 Received: from localhost (localhost.localdomain [127.0.0.1]) by ssel.vub.ac.be (Postfix) with ESMTP id 0F5992468BF5; Tue, 16 Jan 2007 09:32:24 +0100 (CET) X-Virus-Scanned: amavisd-new at ssel.vub.ac.be Received: from ssel.vub.ac.be ([127.0.0.1]) by localhost (ssel.vub.ac.be [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DVvC8tgcMwqz; Tue, 16 Jan 2007 09:32:18 +0100 (CET) Received: from [10.0.4.145] (unknown [10.0.4.145]) by ssel.vub.ac.be (Postfix) with ESMTP id 8036D2468BF3; Tue, 16 Jan 2007 09:32:18 +0100 (CET) In-Reply-To: <200701151956.02144.jon@ffconsultancy.com> References: <200701151956.02144.jon@ffconsultancy.com> Mime-Version: 1.0 (Apple Message framework v752.3) Content-Type: multipart/mixed; boundary=Apple-Mail-4--496908846 Message-Id: <64962DD2-F738-4812-B6BA-29ED5CF1AD75@vub.ac.be> Cc: caml-list@inria.fr From: Bruno De Fraine Subject: Re: [Caml-list] kth smallest element Date: Tue, 16 Jan 2007 09:32:15 +0100 To: Jon Harrop X-Mailer: Apple Mail (2.752.3) X-OriginalArrivalTime: 16 Jan 2007 08:32:24.0130 (UTC) FILETIME=[D8D03220:01C73948] X-Miltered: at concorde with ID 45AC8D98.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; initialized:01 universiteit:01 vub:98 2007,:98 vub:98 wrote:01 caml-list:01 element:03 element:03 bruno:04 bruno:04 applied:04 size:95 modify:05 kth:05 X-Attachments: type="application/octet-stream" name="extSet.ml" name="extSet.ml" type="application/octet-stream" name="extSet.mli" name="extSet.mli" --Apple-Mail-4--496908846 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed On 15 Jan 2007, at 20:56, Jon Harrop wrote: > Anyone got code for the kth smallest element in a list that I can > borrow? I have code for a set that can be limited to a certain size. While you add a potentially very large number of elements, the set will retain the 30 largest elements it has seen up to that point (given that the set was initialized with bound 30). You could modify the code to keep track of the smallest elements instead. Regards, Bruno --Apple-Mail-4--496908846 Content-Transfer-Encoding: 7bit Content-Type: application/octet-stream; x-unix-mode=0644; name=extSet.ml Content-Disposition: attachment; filename=extSet.ml module type KeyedType = sig type t type key val get_key : t -> key end ;; module type S = sig type elt type t val empty : int option -> t val add : elt -> t -> t val cardinal : t -> int val iter : (elt -> unit) -> t -> unit val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a end ;; let at_bound b c = match b with | Some m -> c >= m | None -> false ;; module Make(Kyd: KeyedType) = struct type elt = Kyd.t ;; module Ord = struct type t = Kyd.t ;; let compare a b = let k1 = Kyd.get_key a and k2 = Kyd.get_key b in let res = Pervasives.compare k1 k2 in if res <> 0 then res else Pervasives.compare a b ;; end ;; module OrdSet = Set.Make(Ord) ;; (* implementation through bound, count and set *) type t = (int option * int * OrdSet.t) ;; let empty b = (b,0,OrdSet.empty) ;; let add x (b,c,s) = if c <> 0 && at_bound b c then let cand = OrdSet.min_elt s in if (Ord.compare x cand) < 0 then (b,c,s) else (b,c,OrdSet.add x (OrdSet.remove cand s)) else (b,c+1,OrdSet.add x s) ;; let cardinal (_,c,_) = c ;; let iter f (_,_,s) = OrdSet.iter f s ;; let fold f (_,_,s) a = OrdSet.fold f s a ;; end --Apple-Mail-4--496908846 Content-Transfer-Encoding: 7bit Content-Type: application/octet-stream; x-unix-mode=0644; name=extSet.mli Content-Disposition: attachment; filename=extSet.mli (* A set, ordered according to some key, and optionally bounded to a certain size *) module type KeyedType = sig type t type key val get_key : t -> key end module type S = sig type elt type t val empty : int option -> t val add : elt -> t -> t val cardinal : t -> int val iter : (elt -> unit) -> t -> unit val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a end module Make(Kyd: KeyedType): S with type elt = Kyd.t --Apple-Mail-4--496908846 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed -- Bruno De Fraine Vrije Universiteit Brussel Faculty of Applied Sciences, INFO - SSEL Room 4K208, Pleinlaan 2, B-1050 Brussels tel: +32 (0)2 629 29 75 fax: +32 (0)2 629 28 70 e-mail: Bruno.De.Fraine@vub.ac.be --Apple-Mail-4--496908846--