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

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

[Krishnaswami, Neel]

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

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

[Chris Hecker]

>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.

I've seen this "argument against" a number of times before on this list (like when people wanted constants in patterns), and I don't understand it.  What's the rationale for trying to protect the programmer from making slow code at the expense of useful and expressive features?

Chris

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

[Caml-list] Views

[Chris Hecker]

> 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

Those are excellent!  Exactly what I wanted and have wanted for a while when I realized that pattern matching didn't work on abstract types.  Is there any chance of getting something like this into ocaml?  What do the INRIA folks think about the idea?

Chris


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

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

[Brian Rogoff]

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

[Caml-list] indent 2

[Alexander V. Voinov]

Hi All,

Is the indentation with the step 2 a _must_ for those who program in
OCaml? I got used 4, and already set all the necessary variables for
caml-mode, so that I get:

let count_range bt lwb upb =
    let bti = (IVB.from_to bt lwb upb) in
    let rec count1 bti n =
	if IVB.ok bti then begin
	    match IVB.next bti with
		Some (k, v, b) ->
		    (printf "in count1 %d %d %b\n" k v b); flush stdout;
		    let n' = if b then n + 1 else n in
		    count1 bti n'
	      |	None -> raise (Failure "this cannot happen")
	end
	else
	    n
    in
    count1 bti 0

Is this horrible/terrible/tolerable/appropriate?

Alexander
-------------------
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

Re: [Caml-list] indent 2

[Pierre Weis]

> Hi All,
> 
> Is the indentation with the step 2 a _must_ for those who program in
> OCaml? I got used 4, and already set all the necessary variables for
> caml-mode, so that I get:
> 
> let count_range bt lwb upb =
>     let bti = (IVB.from_to bt lwb upb) in
>     let rec count1 bti n =
> 	if IVB.ok bti then begin
> 	    match IVB.next bti with
> 		Some (k, v, b) ->
> 		    (printf "in count1 %d %d %b\n" k v b); flush stdout;
> 		    let n' = if b then n + 1 else n in
> 		    count1 bti n'
> 	      |	None -> raise (Failure "this cannot happen")
> 	end
> 	else
> 	    n
>     in
>     count1 bti 0
> 
> Is this horrible/terrible/tolerable/appropriate?
> 
> Alexander
> -------------------
> 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

Instead of answering by a two lines long comment and my version of
the best version of your program, I prefer to redirect you to a more
appropriate and documented source concerning Caml programming styles.

This is a good occasion for me to announce a major rewritting of the
Caml programming guide lines where this question is discussed in the
large among a lot of others concerning style, including where to break
lines in Caml programs, where and why use (or avoid) parens, etc.

          http://pauillac.inria.fr/caml/FAQ/pgl-eng.html
          http://pauillac.inria.fr/caml/FAQ/pgl-fra.html

Each programming problem is normally carefully discussed with
arguments (and counter-arguments, and sometimes
counter-counter-arguments) gathered from observation of a lot of Caml
programs including the Caml compilers source code, and from statements
and advices from some of the best Caml programmers in the world, not
mentionning one of the best source of counter-counter-meta-arguments I
know about Caml programs indentation and syntax problems: the sudden
and not always so kind flamewares that appear, while quietly sitting
for lunch in the INRIA's cafeteria !

However, if there is something new to add to these guidelines, feel
free to drop me a not: I would be glad to translate it in french or
english or even incorporate it as is, if you provide a
translation. Don't hesitate to signal an error either, since this is
the worse situation to face for a guideline writter to incorporate a
bug in the suggested programming style!

Thanks in advance for your help,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


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

RE: [Caml-list] Views

[Manuel Fahndrich]

You might also want to look at a paper I wrote that is not referenced in
Okasaki's paper.

"Statically checkable pattern abstractions", ICFP'97.
http://research.microsoft.com/~maf/papers.htm#Misc 

In that paper we describe under what circumstances pattern matches with
pattern abstractions (views) can still be verified for exhaustiveness
and redundancy. This issue is not addressed in Okasaki's paper due to
the particular semantics he chooses, namely to construct explicit values
for the view and then match on those.

In our paper, we do not construct the view values, but simply generate
bindings for the free pattern variables. This raises a number of issues
w.r.t. the matching semantics, and redundancy and exhaustiveness
checking becomes non-trivial.
At the same time, the pattern matching becomes more expressive, and it
is possible to generate more efficient pattern matching code, without
the need to construct the view values.

The way in which pattern matching becomes more expressive is that one
can write a view pattern
	Contains(x) | Empty
for a list data type

One can then write a pattern

	case e of
	  Contains(5) => (* do case where list contains a 5 *)
            | Contains(x) => (* contains something, but no 5 *)
            | Empty => (* list is empty *)

As the example shows, the view transformation depends on nested
patterns, e.g., the code that runs over the list is different if we
match Contains(5), than if we match Contains(x).
In the latter case, which element should we return, which gets us into
the different possible match semantics (first, any, all).


-Manuel
 


-----Original Message-----
From: Chris Hecker [mailto:checker@d6.com] 
Sent: Friday, July 20, 2001 12:08 PM
To: Krishnaswami, Neel; caml-list@inria.fr
Subject: [Caml-list] Views


> 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

Those are excellent!  Exactly what I wanted and have wanted for a while
when I realized that pattern matching didn't work on abstract types.  Is
there any chance of getting something like this into ocaml?  What do the
INRIA folks think about the idea?

Chris


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