Loading ...
Sorry, an error occurred while loading the content.

Re: "ocaml_beginners"::[] Set.Make with polymorphic type

Expand Messages
  • hmf@inescporto.pt
    ... Ok, I understand now. Never encountered this problem as you describe it. ... Yes, this will do. I can always pick a and use it accordingly. ... In other
    Message 1 of 13 , Aug 18, 2008
    • 0 Attachment
      Jon Harrop wrote:
      > On Sunday 17 August 2008 09:38:11 hmf@... wrote:
      >> 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 ...

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

      >>> Of course, we need more information about your actual program before we
      >>> 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.
      >

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

      >> During this processing I need to keep track of
      >> 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.

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

      > Another solution is to store your metadata outside the tree, e.g.
      > using a weak hash table. Richard Jones gave an excellent description of how
      > that can be done fairly recently.
      >

      Ok, I think you are referring to:
      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.
    • hmf@inescporto.pt
      ... ... 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 polymorphic a.
      Message 2 of 13 , Aug 18, 2008
      • 0 Attachment
        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.

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

        Ok, this is clear. Although in my case I do not compare on the
        polymorphic 'a. Explained later.

        >> I had been using would raise run-time type errors at random moments
        >> 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!
        >

        Sure, if you use them often. I guess I should reconsider their
        usefulness and take greater advantage of what they have to offer.

        ...
        >>> During this processing I need to keep track of 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.
        >
        > You cannot even put them into a list! (what would be the type of it?)

        Note that I am only looking for variables. In fact I compare
        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
        > 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.

        Which is in fact what I do. I only wanted functions that can search,
        store and calculate set difference and intersection of variable ids.
        The content is the expression ('a expr).

        > What behavior
        > 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?

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

        > You may also question your assumption that
        > 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]?
        >

        This is the issue. I use variable sets and maps for parsing and
        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.
        >
        > ------------------------------------
        >
        > Archives up to December 31, 2007 are also downloadable at
        http://www.connettivo.net/cntprojects/ocaml_beginners/
        > 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
        >
        >
        >
        >
      • Peng Zang
        ... Hash: SHA1 ... Just FYI, objects also allow you to do this. Eg: class type [ a] set = object( self) method mem : a - bool method add : a - self
        Message 3 of 13 , Aug 18, 2008
        • 0 Attachment
          -----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-----
        Your message has been successfully submitted and would be delivered to recipients shortly.