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

Set of/inside a recursive type ?

Expand Messages
  • Fabrice Marchant
    Hi ! In order to define a multi-tree with an integer at each node, it is possible to write something like this : type int_tree = Content of int * int_tree list
    Message 1 of 13 , May 1, 2007
    • 0 Attachment
      Hi !

      In order to define a multi-tree with an integer at each node, it is possible to write something like this :

      type int_tree = Content of int * int_tree list

      However, please consider the case where there is not any order for children : it would then be possible to define "sets" of such subtrees instead of "lists" of them.

      Please how to write the :

      module TreeSet = Set.Make( ??? int_tree ???

      and the type definition :

      type int_tree = Content of int * TreeSet

      Thanks

      Fabrice
    • Christopher L Conway
      Fabrice, I don t think this it is possible to recursively define a type and a module in this way (i.e., you want to define TreeSet in terms of int_tree and
      Message 2 of 13 , May 1, 2007
      • 0 Attachment
        Fabrice,

        I don't think this it is possible to recursively define a type and a
        module in this way (i.e., you want to define TreeSet in terms of
        int_tree and int_tree in terms of TreeSet). You could accomplish
        something like this with objects:

        class type ['a] set_obj = object
        method add : 'a -> 'a set_obj
        method all : 'a list
        end

        type 'b tree = Node of 'b * ('b tree) set_obj

        Now, you can define subtypes of set_obj that behave like sets,
        multisets, or lists. What you don't get is the guarantee that every
        node in the tree uses the same instance of set_obj.

        Chris

        On 5/1/07, Fabrice Marchant <fabrice.marchant@...> wrote:
        > Hi !
        >
        > In order to define a multi-tree with an integer at each node, it is possible to write something like this :
        >
        > type int_tree = Content of int * int_tree list
        >
        > However, please consider the case where there is not any order for children : it would then be possible to define "sets" of such subtrees instead of "lists" of them.
        >
        > Please how to write the :
        >
        > module TreeSet = Set.Make( ??? int_tree ???
        >
        > and the type definition :
        >
        > type int_tree = Content of int * TreeSet
        >
        > Thanks
        >
        > Fabrice
        >
        >
        >
        > Archives up to November 11, 2006 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
        >
        >
        >
        >
        >
      • Jon Harrop
        ... Note that OCaml s Sets are ordered whereas lists are not. ... Use mutually recursive modules: # module rec Tree : sig type t = Content of int * TreeSet.t
        Message 3 of 13 , May 1, 2007
        • 0 Attachment
          On Tuesday 01 May 2007 09:33, Fabrice Marchant wrote:
          > Hi !
          >
          > In order to define a multi-tree with an integer at each node, it is
          > possible to write something like this :
          >
          > type int_tree = Content of int * int_tree list
          >
          > However, please consider the case where there is not any order for
          > children : it would then be possible to define "sets" of such subtrees
          > instead of "lists" of them.

          Note that OCaml's Sets are ordered whereas lists are not.

          > Please how to write the :
          >
          > module TreeSet = Set.Make( ??? int_tree ???
          >
          > and the type definition :
          >
          > type int_tree = Content of int * TreeSet

          Use mutually recursive modules:

          # module rec Tree : sig
          type t = Content of int * TreeSet.t
          val compare : t -> t -> int
          end = struct
          type t = Content of int * TreeSet.t
          let compare = compare
          end
          and TreeSet : Set.S = Set.Make(Tree);;
          sig type t = Content of int * TreeSet.t val compare : t -> t -> int end
          and TreeSet : Set.S

          --
          Dr Jon D Harrop, Flying Frog Consultancy Ltd.
          The F#.NET Journal
          http://www.ffconsultancy.com/products/fsharp_journal/?e
        • Jon Harrop
          ... The mutual recursion is between two types, one of which is in a module. To do this, you just put both definitions in a set of mutually recursive modules so
          Message 4 of 13 , May 1, 2007
          • 0 Attachment
            On Tuesday 01 May 2007 13:52, Christopher L Conway wrote:
            > Fabrice,
            >
            > I don't think this it is possible to recursively define a type and a
            > module in this way

            The mutual recursion is between two types, one of which is in a module. To do
            this, you just put both definitions in a set of mutually recursive modules so
            that they can refer to each other.

            --
            Dr Jon D Harrop, Flying Frog Consultancy Ltd.
            The F#.NET Journal
            http://www.ffconsultancy.com/products/fsharp_journal/?e
          • Fabrice Marchant
            Hi Christopher ! ... Thanks for the explanations. I m very sorry : should have told in my question I focus on learning non-O Caml for now. It s enough for me
            Message 5 of 13 , May 1, 2007
            • 0 Attachment
              Hi Christopher !

              >... You could accomplish something like this with objects:
              >
              > class type ['a] set_obj = object
              > method add : 'a -> 'a set_obj
              > method all : 'a list
              > end
              >
              > type 'b tree = Node of 'b * ('b tree) set_obj
              >
              > Now, you can define subtypes of set_obj that behave like sets,
              > multisets, or lists. What you don't get is the guarantee that every
              > node in the tree uses the same instance of set_obj.

              Thanks for the explanations.

              I'm very sorry : should have told in my question I focus on learning non-O Caml for now.
              It's enough for me to learn core language & module system. Will see objects later.
              Apologize again.

              Best regards

              Fabrice
            • Fabrice Marchant
              Many thanks Jon ! ... That s absolutely perfect ! I begin to grasp the core language but have a lot to work on modules... ... I come from C++ ( and its heavy
              Message 6 of 13 , May 1, 2007
              • 0 Attachment
                Many thanks Jon !

                > Use mutually recursive modules:
                > # module rec Tree : sig ...
                > end
                > and TreeSet : Set.S = Set.Make(Tree);;

                That's absolutely perfect !
                I begin to grasp the core language but have a lot to work on modules...

                > Note that OCaml's Sets are ordered whereas lists are not.

                I come from C++ ( and its heavy templates ).
                In STL there are standard sets that are kept in ascending order according to a "low total" comparison function.
                But there are a fast hash_set extension that relies on equal keys comparison.
                A mathematical is not ordered. To follow this behaviour I used hash_set extension.

                What I wanted to say about Set vs Lists :
                * unordered sets : I meant that maths sets {1, 2} = {2, 1}.
                * ordered lists : [1;2]=[2;1] -> bool false.

                Yes, I must feed Set.make with an ordered type.
                However, using AnySet.equal, the results follows mathematical set equality.

                Browsing OCaml libraries, I do not see an OCaml-like hash_set.
                But maybe is there such a module outside standard library ?

                I'm very interested to learn more about this subject.

                Best regards

                Fabrice
              • Dave Benjamin
                ... I had to add a with constraint in order to create any nested TreeSets: module rec Tree : sig type t = Content of int * TreeSet.t val compare : t - t -
                Message 7 of 13 , May 3, 2007
                • 0 Attachment
                  On Tue, 1 May 2007, Jon Harrop wrote:

                  > # module rec Tree : sig
                  > type t = Content of int * TreeSet.t
                  > val compare : t -> t -> int
                  > end = struct
                  > type t = Content of int * TreeSet.t
                  > let compare = compare
                  > end
                  > and TreeSet : Set.S = Set.Make(Tree);;
                  > sig type t = Content of int * TreeSet.t val compare : t -> t -> int end
                  > and TreeSet : Set.S

                  I had to add a "with" constraint in order to create any nested TreeSets:

                  module rec Tree : sig
                  type t = Content of int * TreeSet.t
                  val compare : t -> t -> int
                  end = struct
                  type t = Content of int * TreeSet.t
                  let compare = compare
                  end
                  and TreeSet : Set.S with type elt = Tree.t = Set.Make(Tree)
                • Fabrice Marchant
                  ... David, please, could you show me the code you used to test this structure, in order to teach me ?
                  Message 8 of 13 , May 3, 2007
                  • 0 Attachment
                    > I had to add a "with" constraint in order to create any nested TreeSets:
                    > ...

                    David, please, could you show me the code you used to test this structure, in order to teach me ?
                  • Dave Benjamin
                    ... First, I created an element of type Tree.t: # let elt = Tree.Content (5, TreeSet.empty);; val elt : Tree.t = Tree.Content (5, ) This worked as
                    Message 9 of 13 , May 3, 2007
                    • 0 Attachment
                      On Thu, 3 May 2007, Fabrice Marchant wrote:

                      >> I had to add a "with" constraint in order to create any nested TreeSets:
                      >> ...
                      >
                      > David, please, could you show me the code you used to test this
                      > structure, in order to teach me ?

                      First, I created an element of type Tree.t:

                      # let elt = Tree.Content (5, TreeSet.empty);;
                      val elt : Tree.t = Tree.Content (5, <abstr>)

                      This worked as expected. Next, I tried adding this element to an empty
                      TreeSet:

                      # let set = TreeSet.add elt TreeSet.empty;;
                      Characters 22-25:
                      let set = TreeSet.add elt TreeSet.empty;;
                      ^^^
                      This expression has type Tree.t but is here used with type TreeSet.elt

                      The problem is that OCaml does not know that Tree.t is the same as
                      TreeSet.elt. As a result, TreeSet.elt is abstract; we have no way to
                      create values for that type.

                      By rewriting the type of the TreeSet module to read "Set.S with type elt =
                      Tree.t", we inform OCaml that these types are in fact the same. Now, the
                      above example works:

                      # let elt = Tree.Content (5, TreeSet.empty);;
                      val elt : Tree.t = Tree.Content (5, <abstr>)
                      # let set = TreeSet.add elt TreeSet.empty;;
                      val set : TreeSet.t = <abstr>

                      And we can now construct a new element containing this TreeSet.t:

                      # let elt' = Tree.Content (5, set);;
                      val elt' : Tree.t = Tree.Content (5, <abstr>)

                      Dave
                    • Fabrice Marchant
                      Hi Dave ! Thanks to have given the explanations I needed : very interesting. Sometimes I feel OCaml language seems very natural but it is not so easy that it
                      Message 10 of 13 , May 4, 2007
                      • 0 Attachment
                        Hi Dave !

                        Thanks to have given the explanations I needed : very interesting.
                        Sometimes I feel OCaml language seems very natural but it is not so easy that it appears at first glance.

                        Best regards.

                        Fabrice
                      • Richard Jones
                        ... I wouldn t recommend that people tie themselves into Windows as a platform however. And somehow F# seems to be licensed under a very restrictive license
                        Message 11 of 13 , May 4, 2007
                        • 0 Attachment
                          On Fri, May 04, 2007 at 11:01:56PM +0100, Jon Harrop wrote:
                          > F# is already more advanced than OCaml in many ways and also opens
                          > up Windows programming. I highly recommend it for anyone interested
                          > in working with OCaml.

                          I wouldn't recommend that people tie themselves into Windows as a
                          platform however. And somehow F# seems to be licensed under a very
                          restrictive license (how did they get away with that one? - Did they
                          pay INRIA for a separate source license?)

                          Rich.

                          --
                          Richard Jones
                          Red Hat
                        • Jon Harrop
                          ... Indeed. One gets the impression that INRIA use functors in the Set and Map modules just for the sake of it. The advantage of using functors here is that
                          Message 12 of 13 , May 4, 2007
                          • 0 Attachment
                            On Friday 04 May 2007 18:52, Fabrice Marchant wrote:
                            > Hi Dave !
                            >
                            > Thanks to have given the explanations I needed : very interesting.
                            > Sometimes I feel OCaml language seems very natural but it is not so easy
                            > that it appears at first glance.

                            Indeed. One gets the impression that INRIA use functors in the Set and Map
                            modules just for the sake of it. The advantage of using functors here is that
                            you can statically guarantee that you don't accidentally mix two types of set
                            that use different comparison functions. However, it is clearly quite tedious
                            to use in practice.

                            The F# programming language from Microsoft Research doesn't take this
                            approach. In fact, the language doesn't even provide functors. Consequently,
                            all sets are of the type 'a set and you have polymorphic functions to
                            manipulate them. So you can write:

                            > let map f s = Set.fold (Set.add << f) s Set.empty;;
                            val map : ('a -> 'b) -> 'a set -> 'b set

                            Note the use of the built-in function composition operator <<.

                            Personally, I believe that INRIA solved a small problem but left a big problem
                            in this aspect of their design. Specifically, their approach leaves you open
                            to accidentally applying structural functions to sets impicitly. For example,
                            if you try to use a set as the element type of a hash table in OCaml, your
                            program will break randomly. Or just doing s1 = s2 for sets is wrong.

                            F# fixes this by carrying comparison and hashing functions with all objects.
                            This adds a little overhead but it is always good to sacrifice performance in
                            favor of correctness.

                            F# is already more advanced than OCaml in many ways and also opens up Windows
                            programming. I highly recommend it for anyone interested in working with
                            OCaml.

                            --
                            Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                            The F#.NET Journal
                            http://www.ffconsultancy.com/products/fsharp_journal/?e
                          • Jon Harrop
                            ... F# runs under Linux and Mac OS X as well. ... In what way? I can sell programs that I write in F#. ... Besides legacy, F# has nothing to do with OCaml and
                            Message 13 of 13 , May 4, 2007
                            • 0 Attachment
                              On Friday 04 May 2007 22:57, Richard Jones wrote:
                              > I wouldn't recommend that people tie themselves into Windows as a
                              > platform however.

                              F# runs under Linux and Mac OS X as well.

                              > And somehow F# seems to be licensed under a very restrictive license

                              In what way? I can sell programs that I write in F#.

                              > (how did they get away with that one? - Did they pay INRIA for a separate
                              > source license?)

                              Besides legacy, F# has nothing to do with OCaml and INRIA.

                              --
                              Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                              The F#.NET Journal
                              http://www.ffconsultancy.com/products/fsharp_journal/?e
                            Your message has been successfully submitted and would be delivered to recipients shortly.