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 WAA14835; Thu, 29 Jul 2004 22:01:13 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA13618 for ; Thu, 29 Jul 2004 22:01:11 +0200 (MET DST) Received: from mail6.speakeasy.net (mail6.speakeasy.net [216.254.0.206]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6TK19EV030040 for ; Thu, 29 Jul 2004 22:01:09 +0200 Received: (qmail 28750 invoked from network); 29 Jul 2004 20:01:08 -0000 Received: from shell2.speakeasy.net ([69.17.110.71]) (envelope-sender ) by mail6.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 29 Jul 2004 20:01:08 -0000 Date: Thu, 29 Jul 2004 13:01:07 -0700 (PDT) From: brogoff To: Brian Hurt cc: james woodyatt , Ocaml Trade Subject: Re: [Caml-list] looping recursion In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 41095785.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; brogoff:01 brogoff:01 caml-list:01 recursion:01 woodyatt:01 catenable:01 deques:01 extlib:01 simplistic:01 deques:01 catenable:01 extlib:01 quicksort:01 hashtables:01 prepend:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 29 Jul 2004, Brian Hurt wrote: > On Thu, 29 Jul 2004, james woodyatt wrote: > > On 29 Jul 2004, at 09:12, Brian Hurt wrote: > > > On Thu, 29 Jul 2004, brogoff wrote: > > >> > > >> Some problems are just way easier to solve with imperative programming > > >> though. Have you ever taken a look at purely functional catenable > > >> deques? > > > > > > Just got added to extlib, for the record. A simplistic version that > > > actually isn't that much more complicated than the imperitive > > > implementation. > > > > This is extraordinary! Do you really mean to say the deques are purely > > functional, catenable *and* offering the same complexity as the > > non-persistent implementation? Which algorithm was added to extlib? > > > > The version added is O(1) ammoritized. It has the same problem as > quicksort and hashtables, in that on average about 1 operation in N has > cost O(N), instead of strict O(1). > > The library added was the simplest double list implementation. Basically, > the queue is broken into two parts- a front part and a back part, both > kept in lists. The back part list is kept in reverse order- so to add an > element to the end of the queue, you prepend it to the back part list. > You remove elements from head of the front part queue, and when it's > empty, you replace it with the reverse of the back part list. What you've described so far is a queue. I guess I was really oblique in my message, or I'm just being really obtuse, but what I am basically asking for something that implements this signature (people who don't likw modules, avert your gaze!) module type CatenableDeque = sig type 'a t val empty : 'a t val is_empty : 'a t -> bool val push_first : 'a -> 'a t -> 'a t val first : 'a t -> 'a val rest : 'a t -> 'a t val push_last : 'a -> 'a t -> 'a t val last : 'a t -> 'a val front : 'a t -> 'a t val append : 'a t -> 'a t -> 'a t end and I want to be able to efficiently add at both ends and catenate. I ended up doing this instead module type ImpCatenableDeque = sig type 'a t val make : 'a -> 'a t val of_list : 'a list -> 'a t val to_list : 'a t -> 'a list val first : 'a t -> 'a val last : 'a t -> 'a val prev : 'a t -> 'a t val next : 'a t -> 'a t val insert_first : 'a -> 'a t -> unit val insert_last : 'a -> 'a t -> unit val remove_first : 'a t -> unit val remove_last : 'a t -> unit (** conc_front x y : x is modified so that y is in front, y destroyed *) val conc_front : 'a t -> 'a t -> unit (** conc_back x y : x is modified so that y is in back, y destroyed *) val conc_back : 'a t-> 'a t -> unit val iter : ('a -> unit) -> 'a t -> unit val iteri : (int -> 'a -> unit) -> 'a t -> unit end and yes the implementation is a CS101 style doubly linked list, fraught with peril. It may be mildly interesting to compare performance versus James Woodyatt's version using lazy. If I remember correctly, Kaplan and Tarjan use the term purely functional to exclude lazy in one of their papers, and just allow primitive list ops like car/cdr/cons etc. -- Brian ------------------- 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