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 PAA09209; Fri, 20 Jul 2001 15:18:06 +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 PAA09084 for ; Fri, 20 Jul 2001 15:18:06 +0200 (MET DST) Received: from smtp1.cswv.com (smtp1.cswv.com [4.17.129.17]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f6KDI4b22178 for ; Fri, 20 Jul 2001 15:18:04 +0200 (MET DST) Received: from smtp1.cswv.com ([4.17.129.17]) by smtp1.cswv.com with Microsoft SMTPSVC(5.5.1877.197.19); Fri, 20 Jul 2001 09:18:42 -0400 Received: FROM exchange1.cswv.com BY smtp1.cswv.com ; Fri Jul 20 09:18:41 2001 -0400 Received: by exchange1.cswv.com with Internet Mail Service (5.5.2653.19) id ; Fri, 20 Jul 2001 09:21:23 -0400 Message-ID: From: "Krishnaswami, Neel" To: caml-list@inria.fr Subject: Re: [Caml-list] Dequeues (was Generation of streams is slow) Date: Fri, 20 Jul 2001 09:21:16 -0400 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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). Markus Mottl has implemented the functional double-ended queue structures in Okasaki's _Purely Functional Data Structures_. Look for it at: http://www.ai.univie.ac.at/~markus/ocaml_sources/pure_fun-1.0-2/ > 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? 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. The usual argument for them is that there's a strong temptation to avoid proper data abstraction in ML because pattern-matching is so convenient, and the usual argument against them is that they make estimating the performance costs of pattern-matching impossible, since a match could be an arbitrarily expensive 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 In the meantime, a useful workaround in OCaml is to use folds with keyword arguments. Eg, type regexp = Epsilon | Char of char | Kleene of regexp | Seq of regexp * regexp | Alt of regexp * regexp let fold ~epsilon ~char ~kleene ~seq ~alt = let rec fold' = function | Epsilon -> epsilon | Char c -> char c | Kleene re -> kleene (fold' re) | Seq(a, b) -> seq (fold' a) (fold' b) | Alt(a, b) -> alt (fold' a) (fold' b) in fold' And then instead of doing something like this: let rec fold_case = function | Epsilon -> Epsilon | Char c -> Alt(Char(Char.uppercase c), Char(Char.lowercase c)) | Kleene re -> Kleene (fold_case re) | Seq(a, b) -> Seq(fold_case a, fold_case b) | Alt(a, b) -> Alt(fold_case a, fold_case b) You can write the function like this: let fold_case' = fold ~epsilon: Epsilon ~char: (fun c -> Alt(Char(Char.uppercase c), Char(Char.lowercase c))) ~kleene: (fun re -> re) ~seq: (fun a b -> Seq(a, b)) ~alt: (fun a b -> Alt(a, b)) This is not /quite/ as readable as pattern matching, but IMO it's pretty near it. -- Neel Krishnaswami neelk@cswcasa.com ------------------- 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