Re: [Caml-list] looping recursion

[brogoff <brogoff@speakeasy.net>]

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