Re: [Caml-list] looping recursion

[james woodyatt <jhw@wetware.com>]

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 <jhw@wetware.com>
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