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 JAA01405; Sat, 8 Nov 2003 09:50:00 +0100 (MET) 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 JAA01389 for ; Sat, 8 Nov 2003 09:49:59 +0100 (MET) Received: from bob.west.spy.net (mail.west.spy.net [66.149.231.226]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA88nt111171 for ; Sat, 8 Nov 2003 09:49:58 +0100 (MET) Received: from [192.168.1.196] (dhcp-196.west.spy.net [192.168.1.196]) by bob.west.spy.net (Postfix) with ESMTP id 0C8FF58B6; Sat, 8 Nov 2003 00:49:49 -0800 (PST) In-Reply-To: <20031107124619.GA14374@fistandantilus.takhisis.org> References: <483F0AC5-1105-11D8-AC71-000393CFE6B8@spy.net> <20031107124619.GA14374@fistandantilus.takhisis.org> Mime-Version: 1.0 (Apple Message framework v606) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <8245A4CA-11C8-11D8-95B0-000393CFE6B8@spy.net> Content-Transfer-Encoding: 7bit Cc: Caml Mailing List From: Dustin Sallings Subject: Re: [Caml-list] removing an item from a list efficiently Date: Sat, 8 Nov 2003 00:49:48 -0800 To: Stefano Zacchiroli X-Mailer: Apple Mail (2.606) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 okasaki's:01 figuring:01 prev:01 linked:01 ocaml:01 ocaml:01 mutable:01 mutable:01 imho:01 nov:01 wrote:03 zacchiroli:03 data:03 stefano:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Nov 7, 2003, at 4:46, Stefano Zacchiroli wrote: > IMHO to implement an LRU policy, lists are not the best structures due > to the O(n) limit above. You can consider standard heaps (assuming you > have an upper bound on the number of entries) or binomial heaps (you > can > find an implementation in Okasaki's book). This is really what I was asking, whether ocaml lists could be appropriate. I'm having difficulty figuring out how to implement a double linked list, though. I want something like this: type 'a link = Nothing | Link of 'a t;; type 'a t = { data: 'a; mutable prev: 'a link; mutable next: 'a link; };; But, link and t don't know about each other. How does one go about doing this kind of thing in ocaml? -- Dustin Sallings ------------------- 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