From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id GAA24532; Sat, 21 Jul 2001 06:50:08 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id GAA24499 for <caml-list@pauillac.inria.fr>; Sat, 21 Jul 2001 06:50:08 +0200 (MET DST)
Received: from shell5.ba.best.com (shell5.ba.best.com [206.184.139.136])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f6L4o6H12485
	for <caml-list@inria.fr>; Sat, 21 Jul 2001 06:50:07 +0200 (MET DST)
Received: from localhost (bpr@localhost)
	by shell5.ba.best.com (8.9.3/8.9.2/best.sh) with ESMTP id VAA03696
	for <caml-list@inria.fr>; Fri, 20 Jul 2001 21:50:05 -0700 (PDT)
Date: Fri, 20 Jul 2001 21:50:05 -0700 (PDT)
From: Brian Rogoff <bpr@best.com>
To: caml-list@inria.fr
Subject: Re: [Caml-list] Dequeues (was Generation of streams is slow)
In-Reply-To: <B1E4D3274D57D411BE8400D0B783FF322E8672@exchange1.cswv.com>
Message-ID: <Pine.BSF.4.21.0107202134180.18227-100000@shell5.ba.best.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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