- Jon Harrop wrote:
> On Sunday 17 August 2008 09:38:11 hmf@... wrote:

Ok, I understand now. Never encountered this problem as you describe it.

>> Jon Harrop wrote:

>>> Note that this is exactly

>>> equivalent to the problem that the Set.Make functor itself solves because

>>> it lets you create sets over many different types from factored code but

>>> without parametric polymorphism. Functors also have a very important

>>> advantage over polymorphism in OCaml: they are less error prone.

>> Pardon my ignorance, but how is this so?

>

> You often want to associate functions with a type, such as a custom comparison

> function. Modules let you do this. Polymorphism (in OCaml) does not. Ideally,

> polymorphism should solve this problem as it does in F# or Haskell but OCaml

> does not (yet) have that.

>

> The problem is ...

>>> Of course, we need more information about your actual program before we

Yes, this will do. I can always pick 'a and use it accordingly.

>>> can help you to translate it into a functor-based solution. Can you post

>>> more code?

>> I am (re)developing (part of) a simple first order logic resolution

>> system (à là Prolog). The AST is something like: ...

>

> I'm a little concerned that every single node has its own incompatible 'a. Why

> not do:

>

> type 'a expr_aux =

> | PTrue

> | PFalse

> | Var of sym_id * _type

> | Atom of sym_id * _type

> | Pred of sym_id * _type * 'a expr list

> | And of 'a expr * 'a expr

> | Or of 'a expr * 'a expr

> | Cond of 'a expr * 'a expr

> | BiCond of 'a expr * 'a expr

> | Not of 'a expr

> and 'a expr = { meta: 'a; expr: 'a expr_aux }

>

> Such factorings should make it much easier to develop your code.

>

>> During this processing I need to keep track of

In other words, separate 'a from 'a expr and give it a specific type.

>> the variables. I need maps and sets where the

>> id of the variable is used as a key. However, I

>> want to keep these variable sets irrespective of

>> the "'a"'s type. hence the question: can I define

>> an ordered type whose type is polymorphic and use

>> that in a Set or Map.

>

> The "irrespective of "'a"s type" sounds like a problem for a functor-based

> solution.

> Another solution is to store your metadata outside the tree, e.g.

Ok, I think you are referring to:

> using a weak hash table. Richard Jones gave an excellent description of how

> that can be done fairly recently.

>

http://caml.inria.fr/pub/ml-archives/caml-list/2007/08/aa1a229f9e73e7a2ad52e8e5b79970e3.en.html

I am taking a look at it.

Thank you for the information. - Christophe TROESTLER wrote:
> On Sun, 17 Aug 2008 12:59:11 +0100, Jon Harrop wrote:

...

>> The problem is that you must avoid using the built-in polymorphic functions

>> (e.g. =, compare and hash) on non-trivial data structures because they

>> silently break, either causing corruption or generating run-time type errors.

>

> To be more precise: the polymorphic comparison raises the

> Invalid_argument exception on abstract and functional values:

>

> # let f x = x + 1;;

Good to have these examples. Makes Jon's

explanations much clearer.

>

Ok, this is clear. Although in my case I do not compare on the

>> (...) I made the mistake of using a polymorphic expr type (just as

>> you are) only to develop it by placing functions and sets inside

>> exprs. Then the = and hash functions (...)

>

> To clarify for Hmf, applying = to sets will not raise exceptions

> (provided their content supports = ) but the equality will be weaker

> than the equality of sets (i.e. if [s1 = s2] then [Set.equal s1 s2]

> but not necessarily the other way around because = is the equality of

> the internal representation of sets). If you have a polymorphic

> type, you indeed better provide a "compare" function (parametrized by

> an ordered content module if comparison depends on the contents --

> look at Set.Make for an example).

>

polymorphic 'a. Explained later.

>> I had been using would raise run-time type errors at random moments

Sure, if you use them often. I guess I should reconsider their

>> and I was unable to fix the program without a complete rewrite.

>

> Well, couldn't you can ask for a stack trace to locate the origin of

> your exception? Or you could have undefined = (and possibly all other

> comparison operators) and let the compiler walks you through all your

> uses of it.

>

>> ...

>>> All that and the fact that the use of modules is not trivial, even for

>>> those well versed in the theory and practice of Ocaml.

>> I think modules are only perceived to be difficult because there is little

>> tutorial information about them.

>

> Hmf, be not intimidated by functors, they are an easy and natural concept!

>

usefulness and take greater advantage of what they have to offer.

...>>> During this processing I need to keep track of the variables. I

Note that I am only looking for variables. In fact I compare

>>> need maps and sets where the id of the variable is used as a

>>> key. However, I want to keep these variable sets irrespective of

>>> the "'a"'s type. hence the question: can I define an ordered type

>>> whose type is polymorphic and use that in a Set or Map.

>

> You cannot even put them into a list! (what would be the type of it?)

variable's ids (other expression types have no ids). Currently I

store only the ids or map an id to a tuple (id,'a expr).

Comparison is on ids only, not on the 'a expr (ordered type of

'a expr, if it were possible, would just use id's of variables and

possibly raise exception on others).

> There are several ways around it depending on what you want to do with

Which is in fact what I do. I only wanted functions that can search,

> these sets:

>

> - use a variant type for 'a (that will allow for AST that mix various

> tags);

>

> - use a variant type for the elements of your set (probably the closer

> to what you desire, you need to know all instances of 'a in advance);

>

> - A variant of the above is to use a record for 'a, leaving unused

> capabilities to None (that requires you identify all possibilities

> in advance);

>

> - Hide 'a altogether when you put the expressions in your set,

> i.e. provide a function ['a expr -> t]. You can use

> http://ocaml.janestcapital.com/?q=node/18 as an inspiration. Of

> course the function [t -> 'a expr] may raise an exception but this

> is flexible, you can use "unexpected" 'a provided you know the

> conversion functions. You can provide a safe [t -> unit expr] to

> still be able to pattern match on the AST without accessing the

> value in 'a;

>

> - Use polymorphic variants to instantiate 'a, then you can use

> subtyping to coerce your expressions to the lower common denominator;

>

> - Use id's that already carry the type information ([get : set -> 'a

> id -> 'a expr] is ok).

>

> All solutions will need to "hide" in some way the value of 'a because

> various 'a reflects "capabilities" of your expressions.

store and calculate set difference and intersection of variable ids.

The content is the expression ('a expr).

> What behavior

Return two 'a expr. or a tuple of ('a expr, 'a)

> do you expect if you ask the "previous occurrence of a variable were a

> clashing quantifier was detected" to an element of your set that does

> not have that capability?

> You may also question your assumption that

This is the issue. I use variable sets and maps for parsing and

> you need to store these expressions irrespective of 'a. Wouldn't you

> prefer various storages, parametrized by 'a, that reflects the

> different capability of your expressions? Say with functions like

> [clashing_quantifiers : loc expr set -> loc_clash expr set]?

>

detecting syntax errors but I also use these to convert formula

to their conjunctive normal form (and possibly other stuff like

unification). So I was hoping to have a set of these functions

use throughout independently of what 'a is. Of course this is

not strictly necessary and the above is possible.

> Hope it helps,

Yes it has.

Thank you.

> C.

http://www.connettivo.net/cntprojects/ocaml_beginners/

>

> ------------------------------------

>

> Archives up to December 31, 2007 are also downloadable at

> The archives of the very official ocaml list (the seniors' one) can be found

at http://caml.inria.fr

> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo!

Groups Links

>

>

>

> - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

On Monday 18 August 2008 03:01:00 am hmf@... wrote:

> > You often want to associate functions with a type, such as a custom

> > comparison function. Modules let you do this. Polymorphism (in OCaml)

> > does not. Ideally, polymorphism should solve this problem as it does in

> > F# or Haskell but OCaml does not (yet) have that.

> >

> > The problem is ...

>

> Ok, I understand now. Never encountered this problem as you describe it.

Just FYI, objects also allow you to do this. Eg:

class type ['a] set = object('self)

method mem : 'a -> bool

method add : 'a -> 'self

method remove : 'a -> 'self

...

method equals : 'a set -> bool

method compare : 'a set -> int

method hash : unit -> int

end

Peng

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFIqVnRfIRcEFL/JewRAgdhAJ9ZK+KPTg5vaGLrZ+rPGxOvje6mRwCcDP8k

DZ8uEuSC4wO/vvozEOefkuY=

=0xEV

-----END PGP SIGNATURE-----