Re: [Caml-list] Dequeues (was Generation of streams is slow)

[Brian Rogoff <bpr@best.com>]

On Fri, 20 Jul 2001, Krishnaswami, Neel wrote:
> Chris Hecker [mailto:checker@d6.com] wrote:
> > 
> > Has anybody written a simple "circular linked list" 
> > implementation in ocaml?  Basically, you'd want it to act 
> > exactly like the built in lists, but appends and finding the 
> > tail elemeent are O(1).

I appended a simple circular linked list module to this message. Not
tested, but it type checks ;-). It should be close enough, but be warned,
it's evil imperative code. 

> > It doesn't seem possible to make this as convenient as the 
> > built in list, since :: doesn't seem to be redefinable, and I 
> > don't know how you'd make this work in pattern matching.  Is 
> > there any work on making user defined abstract types work in 
> > pattern matching?

I don't think that pattern matching buys you much with the imperative
lists. 

> IIRC, the ability to pattern-match on abtract types is called 
> called "views". There are a number of proposals for adding
> them to the ML family, but I'm not really competent to judge
> between them. 

> function call. Personally, I like views; here are some references
> so you can judge for yourself:
> 
> http://www.cs.columbia.edu/~cdo/papers.html#ml98views
> http://cm.bell-labs.com/cm/cs/who/wadler/papers/view/view.dvi
> http://www.cs.orst.edu/~erwig/papers/abstracts.html#IFL96

As long as you're there at Martin Erwig's page see 

http://www.cs.orst.edu/~erwig/papers/abstracts.html#Haskell00

too. Much of that was influenced by his (very cool) functional graph
library. 

In addition to the "folds with keyword arguments" trick you show,
there was also a similar approach mentioned on c.l.functional of defining
an external type to match your abstract one, and that trick even works in
SML. I think with polymorphic variants that trick is even a little nicer.  

-- Brian

(* circlist.mli *)
type 'a t
val make : 'a -> 'a t
val peek_front   : 'a t -> 'a
val peek_back   : 'a t -> 'a
val push_front : 'a -> 'a t -> 'a t
val push_back : 'a -> 'a t -> 'a t 
val pop_front : 'a t -> 'a
val insert_front : 'a t -> 'a t -> unit
val insert_back : 'a t-> 'a t -> unit
val iter : ('a -> unit) -> 'a t -> unit
val map : ('a -> 'b) -> 'a t -> 'b t

(* circlist.ml *)
type 'a t = { data :'a; mutable next : 'a t }

let make v =
  let rec x = {data = v; next = x} in 
  x 

let peek_front l  = l.next.data
let peek_back l  = l.data

let push_front e l  = 
  let new_first = {data = e; next = l.next} in 
  (l.next <- new_first; l)

let push_back e l  = 
  let new_last = {data = e; next = l.next} in 
  (l.next <- new_last; new_last)

let pop_front l = 
  if l == l.next then 
    failwith "Circlist.pop_front"
  else
    let result = l.next.data in 
    (l.next <- l.next.next; result)

(* insert elems into the front of l, returning modified l *)
let insert_front elems l =
  let front = elems.next in 
  (elems.next <- l.next; 
   l.next <- front;
   l)

(* insert elems at the back of l, returning modified 
   elems (which is last) 
*)
let insert_back elems l =
  let front = l.next in 
  (l.next <- elems.next;
   elems.next <- front; 
   elems)

let iter f l = 
  let rec loop cl = 
    if cl == l then f cl.data
    else (f cl.data; loop cl.next) in 
  loop l.next

let map f l = 
  let r = ref [] in 
  (iter (fun v -> r := (f v)::!r) l;
   let result = make (List.hd !r) in 
   List.iter (fun v -> ignore (push_front v result)) (List.tl !r);
   result)


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr