This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] looping recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-07-29 (20:01) From: brogoff Subject: Re: [Caml-list] looping recursion
```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

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

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

```