English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] Dequeues (was Generation of streams is slow)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-07-21 (04:50)
From: Brian Rogoff <bpr@b...>
Subject: Re: [Caml-list] Dequeues (was Generation of streams is slow)
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

> 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 


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

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 

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"
    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;

(* 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; 

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);

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