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 GAA05788; Fri, 30 Jul 2004 06:42:58 +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 GAA05714 for ; Fri, 30 Jul 2004 06:42:57 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from wetware.com (wetware.wetware.com [199.108.16.1]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6U4gtEV017372 for ; Fri, 30 Jul 2004 06:42:56 +0200 Received: from [208.177.152.17] (helo=[10.0.1.9]) by wetware.com with esmtp (Exim 4.20) id 1BqPEM-000736-A5; Thu, 29 Jul 2004 21:42:54 -0700 Mime-Version: 1.0 (Apple Message framework v618) In-Reply-To: References: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: james woodyatt Subject: Re: [Caml-list] looping recursion Date: Thu, 29 Jul 2004 21:42:53 -0700 To: brogoff , Ocaml Trade X-Mailer: Apple Mail (2.618) X-Miltered: at nez-perce with ID 4109D1CF.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; woodyatt:01 jhw:01 wetware:01 caml-list:01 recursion:01 brogoff:01 obtuse:01 avert:99 val:01 val:01 doubly:01 extlib:01 deque:01 worst-case:01 allocations:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On 29 Jul 2004, at 13:01, brogoff wrote: > > 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. > [...] > 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. They do. Mine would be purely functional if it didn't have to support concatenation. And it does not suffer from the limitations of the implementation Mr. Hurt is talking about in the recent addition to Extlib. I would expect to pay a small price for the persistence. With the imperative double-link list, the insert operation costs one allocation, a reference copy and the update to the links. With my functional deque, the insert operation costs at least one allocation, possibly as many, in the worst-case, as 2/3 log[2] N allocations (where N is the number of elements in the deque), and the link update overhead. The cost of all the other operations is similar in complexity. Here is the module interface file... (*---------------------------------------------------------------------- -----* INTERFACE cf_deque.mli Copyright (c) 2003-2004, James H. Woodyatt All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *----------------------------------------------------------------------- ----*) (** A functional persistent double-ended catenable deque, with O{_ avg}(1) cost for every operation. Internally, this is a recursive data structure with height O(log N). *) (** The abstract type of a deque. *) type +'a t (** The empty deque. *) val nil: 'a t (** Returns [true] if the deque is the empty deque. *) val empty: 'a t -> bool (** Functions for operations on one of the two ends of a deque. *) module type Direction_T = sig (** [push x d] adds the element [x] to the end of the deque [d]. The average cost is constant. Worst-case running time is O(log N), which happens once in every N operations. Not tail-recursive. *) val push: 'a -> 'a t -> 'a t (** [pop d] returns [None] if [d] is the empty deque, otherwise it returns [Some (x, d')] where [x] is the element on the end of the deque, and [d'] is the remainder of [d] with the element [x] removed. The average cost is constant. Worst-case running time is O(log N), which happens once in every N operations. Not tail-recursive. *) val pop: 'a t -> ('a * 'a t) option (** [head d] returns the element at the end of the deque [d]. Raises [Not_found] if the deque is empty. Not tail-recursive. *) val head: 'a t -> 'a (** [tail d] is discards the element at the end of the deque [d]. Raises [Not_found] if the deque is empty. Not tail-recursive. *) val tail: 'a t -> 'a t (** [to_seq d] returns a lazily evaluated sequence of the elements in the deque in the order they would appear by successive calls of [pop d]. *) val to_seq: 'a t -> 'a Cf_seq.t (** [to_seq2 d] returns a lazily evaluated sequence of the pairs [(hd, tl)] obtained by successively calling of [pop d]. *) val to_seq2: 'a t -> ('a * 'a t) Cf_seq.t end module A: Direction_T (** Operations on the left end of a deque. *) module B: Direction_T (** Operations on the right end of a deque. *) (** [iterate f d] applies [f] to every element in [d] in left-to-right order. Not tail recursive. *) val iterate: ('a -> unit) -> 'a t -> unit (** [predicate f d] returns [true] if the result of applying [f] to every element in the deque [d] is [true], or if [d] is the empty deque. The order in which elements are applied is left to right. If [f] returns [false], then no more elements from [d] will be applied and the result will be returned immediately. Not tail recursive. *) val predicate: ('a -> bool) -> 'a t -> bool (** [fold f a0 d] is [f (... (f (f a0 e0) e1) ...) en] when [e0..en] are the elements of the deque [d] in left-to-right order. Not tail recursive. *) val fold: ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b (** [filter f d] returns a new deque composed by applying [f] to every element in [d], including only those elements for which the result is [true]. The function is applied to the elements in the deque in left-to-right order. Not tail recursive. *) val filter: ('a -> bool) -> 'a t -> 'a t (** [map f d] returns a new deque composed by applying [f] to every element in [d] in left-to-right order. Not tail recursive. *) val map: ('a -> 'b) -> 'a t -> 'b t (** [optmap f d] returns a new deque composed by applying [f] to every element in [d] in left-to-right order, including only those elements of [d] for which [f] returns [Some] value. Not tail recursive. *) val optmap: ('a -> 'b option) -> 'a t -> 'b t (** [listmap f d] returns a new deque composed by applying [f] to every element in [d] in left-to-right order, taking all the resulting lists of elements in order. Not tail recursive. *) val listmap: ('a -> 'b list) -> 'a t -> 'b t (** [seqmap f d] returns a new deque composed by applying [f] to every element in [d] in left-to-right order, taking all the resulting sequences of elements in order. Not tail recursive. *) val seqmap: ('a -> 'b Cf_seq.t) -> 'a t -> 'b t (** [partition f s] returns two deques. The first is the deque of elements in [d] for which applying [f] results in [true], and the second is the deque of elements for which applying [f] results in [false]. The elements are applied in left-to-right order. *) val partition: ('a -> bool) -> 'a t -> 'a t * 'a t (** [length d] computes the number elements contained in the deque [d]. Not tail recursive. *) val length: 'a t -> int (** [catenate d1 d2] returns a new deque composed by joining the right end of [d1] to the left end of [d2]. The average cost is constant. Not tail-recursive. *) val catenate: 'a t -> 'a t -> 'a t (*--- End of File [ cf_deque.mli ] ---*) NOTE: it turns out that I will be changing the module in the next release, specifically to make the utility functions [iterate, predicate, filter, map, fold, etc.] apply their iterative function in left-to-right order, rather than an indeterminate order. The right-to-left order will require converting the deque to a sequence and using the [Cf_seq] function of the same name. -- j h woodyatt markets are only free to the people who own them. ------------------- 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