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

["Krishnaswami, Neel" <neelk@cswcasa.com>]

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