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

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

Expand Messages
  • 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 1 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 2 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.