Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)

[brogoff@speakeasy.net]

On Sun, 4 May 2003, John Max Skaller wrote:
> Mattias Waldau wrote:
> > Languages like PHP have more advanced built-in datastructures with
> > language syntax to support them. In Ocaml, we can create the same
> > program, however, there is no syntax support, and we have to add
> > declarations like
> > 
> > module StringSet = Set.Make(struct 
> >       type t = string
> >       let compare = compare
> >     end) ;;
> > 
> > It would be nice if the typechecker could deduce the type of the set and
> > add the above declaration automatically to the program. That would make
> > it easier for beginners to use the advanced datastructures of Ocaml.

As someone else points out, you have the source, you can make polymorphic 
versions of sets/maps/... by coding polymorphic versions of the source and  
instantiating with modules based on polymorphic comparisons.

> The problem is worse than that. There are places you need such
> an animal but CANNOT have it. This occurs when there is type
> recursion involved and the lack of orthogonality in Ocaml syntax
> prevents you actually declaring the functor instance
> at the point you need it.

It isn't a syntax problem. I agree that the lack of recursion in the module 
system is a big problem that needs to be fixed (pun intended ;-) but I 
think you (and, more importantly, the FAQ maintainer) should mention that 
there ARE workarounds to these problems. There was a recent discussion 
on this topic here (and in comp.lang.ml, a 2 year long thread!) where you 
can see them. Briefly, the polymorphic sets I just mentioned can be used 
to build simple recursive structures using the parameterization trick at the 
level of types (i.e., a type variable is used to "defer" the instantiation and 
allow you to tie the knot. To build more complex ones, you need to recode 
Set (or whatever functor) to be a functor on an "open" ordered type; the 
comparison function must be parameterized so that you can close the recursion 
later. So, this is the parameterization trick allowed the level of types and 
functions simultaneously. Jean Claude Filliatre showed that one on his message 
on this topic. I haven't tried it with classes, so YMMV. 

The only minor annoyance with that trick is that it requires some textual 
duplication on account of the scope rules for "with type" constraints. This 
is annoying, and I think, syntactic. 

> Result: dont use functors, they're not properly
> supported.

Nonsense. There are places where there can be improvements, but this is as 
whacky as the "don't use lists" assertion. Why are you using classes? Are they 
properly supported?

> I found this really annoying. It applies in
> other parts of the language too, for example
> polymorphic variants. Here again, the very
> feature functional languages are supposed to
> understand best -- recursion -- is actually
> handled better in C++.

Get outta here!

> I need variants whose arguments include the variant
> 
> type, and I can't have them together with subtyping.
> Yet for someone representing
> a programming language recursion is natural.
> 
> type x = [`A | `B of y]
> and y = [x | `C of x]
> 
> There is no problem doing this with textual substitution:
> 
> type x = [`A | `B of y]
> and y = [`A | `B of y | `C of x]

Yup, that's annoying. I was nailed by the same problem recently, and I 
used polymorphism to avoid having to write the tags more than once. Something 
like this 

type 'a x' = [`A | `B of 'a]
type x = y x' and y = [y x' | `C of x] 

or something like that, I don't recall. Maybe Jacques will shed some light on 
this restriction. 

Someone else addresses your subtyping issue. 

I have to admit that I have found polymorphic variants puzzling at times, 
but the additional power is amazing and allows you to get at the extensibility 
of OO and beyond. Look up "The Expression Problem" on Google and see if you 
can find a discussion on the defunct Java Genericity mailing list. Or just 
take a look at Jacques Garrigues little paper on code reuse with variants. 
I'm using the same approach to model a different domain than lambda calculus 
evaluators, and while the (algorithmic) complexity of that domain makes 
the evaluator and types a bit more complex, the basic ideas translate easily. 
What a cool language!

-- Brian


-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners