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

Re: "ocaml_beginners"::[] What is the best way to code this data structure?

Expand Messages
  • Dan Bensen
    ... That s what I wrote in my second response. You can ignore the first one. ... Your solution is okay. The problem is messy. [Non-text portions of this
    Message 1 of 12 , Oct 31, 2012
    • 0 Attachment
      > No, X, O, and S are different types of data.

      That's what I wrote in my second response.
      You can ignore the first one.

      > What I suggested in my initial email
      > ... seems unnecessarily messy.

      Your solution is okay. The problem is messy.


      [Non-text portions of this message have been removed]
    • Gabriel Scherer
      I m fine with your solution (sometimes it s a good choice to get weaker static guarantees for less conceptual complexity), but I would like to point out that
      Message 2 of 12 , Nov 1, 2012
      • 0 Attachment
        I'm fine with your solution (sometimes it's a good choice to get
        weaker static guarantees for less conceptual complexity), but I would
        like to point out that the polymorphic variant solution suggested by
        Lukasz should work as well, and propose a simpler solution based on
        irregular recursion:

        Lukasz-inspired solution:

        type ('x, 'o) lu = [ `X of 'x * ('x, 'o) ld | `S ]
        and ('x, 'o) ld = [ `O of 'o * ('x, 'o) ld | `S ]

        let rec iter doX doO doXS doOS = function
        | `S -> ()
        | `X (x, `S) -> doXS x
        | `O (o, `S) -> doOS o
        | `X (x, rest) -> doX x; iter doX doO doXS doOS rest
        | `O (o, rest) -> doO o; iter doX doO doXS doOS rest

        let () = iter print_int print_string (Printf.printf "%d\n") print_endline
        (`X (1, `O ("o", `X (2, `O ("oo", `S)))))


        Irregular recursive datatype:

        type ('x, 'o) alterning =
        | Stop
        | One of 'x * ('o, 'x) alterning

        (* abbreviation just to have a shorter signature *)
        type 't u = 't -> unit

        let rec iter : 'x 'o. 'x u -> 'o u -> 'x u -> 'o u -> ('x, 'o) alterning u =
        fun do1 do2 do1S do2S ->
        function
        | Stop -> ()
        | One (x, Stop) -> do1S x
        | One (x, rest) -> do1 x; iter do2 do1 do2S do1S rest

        let () = iter print_int print_string (Printf.printf "%d\n") print_endline
        (One (1, One ("o", One (2, One ("oo", Stop)))))

        The recursion pattern here is "irregular" because the recursive
        occurence of "alternating" is done at a different type from its
        definition (('o, 'x) vs. ('x, 'o)). The corresponding "iter" function
        is therefore a so-called "polymorphic recursion", which does something
        non-obvious with typing, and needs an explicit polymorphic annotation
        (added since OCaml 3.12) to proceed.
        (In slightly more details, the way recursive function are inferred in
        ML is to pick a monomorphic type for them, type their body, and then
        generalize what can be generalize; doing this on a function that calls
        itself at a type different than its declaration will result in too
        much unification and a weaker type than you want.)

        On Thu, Nov 1, 2012 at 1:28 AM, Dan Bensen <danbensen@...> wrote:
        >> No, X, O, and S are different types of data.
        >
        > That's what I wrote in my second response.
        > You can ignore the first one.
        >
        >> What I suggested in my initial email
        >> ... seems unnecessarily messy.
        >
        > Your solution is okay. The problem is messy.
        >
        >
        > [Non-text portions of this message have been removed]
        >
        >
        >
        > ------------------------------------
        >
        > Archives up to December 31, 2011 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
        >
        >
        >
      • Max Hayden Chiz
        On Thu, Nov 1, 2012 at 3:04 AM, Gabriel Scherer ... Thank you for your help. I think this is probably the best way to go, but I m not sure how to figure out
        Message 3 of 12 , Nov 1, 2012
        • 0 Attachment
          On Thu, Nov 1, 2012 at 3:04 AM, Gabriel Scherer
          <gabriel.scherer@...>wrote:

          > **
          >
          >
          > I'm fine with your solution (sometimes it's a good choice to get
          > weaker static guarantees for less conceptual complexity), but I would
          > like to point out that the polymorphic variant solution suggested by
          > Lukasz should work as well, and propose a simpler solution based on
          > irregular recursion:
          >
          > Lukasz-inspired solution:
          >
          > type ('x, 'o) lu = [ `X of 'x * ('x, 'o) ld | `S ]
          > and ('x, 'o) ld = [ `O of 'o * ('x, 'o) ld | `S ]
          >
          > let rec iter doX doO doXS doOS = function
          > | `S -> ()
          > | `X (x, `S) -> doXS x
          > | `O (o, `S) -> doOS o
          > | `X (x, rest) -> doX x; iter doX doO doXS doOS rest
          > | `O (o, rest) -> doO o; iter doX doO doXS doOS rest
          >
          > let () = iter print_int print_string (Printf.printf "%d\n") print_endline
          > (`X (1, `O ("o", `X (2, `O ("oo", `S)))))
          >
          > Irregular recursive datatype:
          >
          > type ('x, 'o) alterning =
          > | Stop
          > | One of 'x * ('o, 'x) alterning
          >
          > (* abbreviation just to have a shorter signature *)
          > type 't u = 't -> unit
          >
          > let rec iter : 'x 'o. 'x u -> 'o u -> 'x u -> 'o u -> ('x, 'o) alterning u
          > =
          > fun do1 do2 do1S do2S ->
          > function
          > | Stop -> ()
          > | One (x, Stop) -> do1S x
          > | One (x, rest) -> do1 x; iter do2 do1 do2S do1S rest
          >
          Thank you for your help. I think this is probably the best way to go, but
          I'm not sure how to figure out if the head of the list is 'x or 'o so that
          I can pass the right do functions to iter.

          Someone else had suggested something similar to this, but in order to be
          able to start the recursion, it seemed like I had to have an extra type:

          type mylist = X of (xdata,odata) alternating | O of (odata, xdata)
          alternating

          Is that right or is there a way to do away with this extra step?


          [Non-text portions of this message have been removed]
        • Lukasz Stafiniak
          ... Thanks, nice example of polymorphic recursion! Thank you for your help. I think this is probably the best way to go, but ... first. The unfortunate thing
          Message 4 of 12 , Nov 1, 2012
          • 0 Attachment
            On Thu, Nov 1, 2012 at 5:22 PM, Max Hayden Chiz <max.chiz@...> wrote:

            > **
            >
            >
            > On Thu, Nov 1, 2012 at 3:04 AM, Gabriel Scherer
            > <gabriel.scherer@...>wrote:
            > >
            > > Irregular recursive datatype:
            > >
            > > type ('x, 'o) alterning =
            > > | Stop
            > > | One of 'x * ('o, 'x) alterning
            > >
            > > (* abbreviation just to have a shorter signature *)
            > > type 't u = 't -> unit
            > >
            > > let rec iter : 'x 'o. 'x u -> 'o u -> 'x u -> 'o u -> ('x, 'o) alterning
            > u
            > > =
            > > fun do1 do2 do1S do2S ->
            > > function
            > > | Stop -> ()
            > > | One (x, Stop) -> do1S x
            > > | One (x, rest) -> do1 x; iter do2 do1 do2S do1S rest
            > >
            >
            Thanks, nice example of polymorphic recursion!

            Thank you for your help. I think this is probably the best way to go, but
            > I'm not sure how to figure out if the head of the list is 'x or 'o so that
            > I can pass the right do functions to iter.
            >
            > The type system will keep reminding you which kind of elements comes
            first. The unfortunate thing is you will not be able to neither "just not
            care", nor "be prepared for both cases" -- the type system will require
            that in a single function you only allow one type of elements to come first
            in your list.



            > Someone else had suggested something similar to this, but in order to be
            > able to start the recursion, it seemed like I had to have an extra type:
            >
            > type mylist = X of (xdata,odata) alternating | O of (odata, xdata)
            > alternating
            >
            > Is that right or is there a way to do away with this extra step?
            >

            This extra step remembers which kind of elements comes first, so that some
            parts of your code can be agnostic about it, and other can handle both
            cases by a single function. I think it's "right" (i.e. to avoid this step
            and not introducing other complications you would need to go back to
            polymorphic variant solution).


            [Non-text portions of this message have been removed]
          • danbensen@att.net
            ... type x = int type o = string type s = string type xos_list = { o0o: o option; xos: (x*o) list; xfo: x option; s: s } let do_some f = function None - () |
            Message 5 of 12 , Nov 1, 2012
            • 0 Attachment
              > I'm not sure how to figure out if the head of the list is 'x or 'o

              type x = int
              type o = string
              type s = string

              type xos_list = {
              o0o: o option;
              xos: (x*o) list;
              xfo: x option;
              s: s }

              let do_some f = function None -> () | Some x -> f x

              let rec iter do_x do_o { o0o; xos; xfo; _ } =
              do_some do_o o0o; List.iter (fun (x,o) -> do_x x; do_o o) xos;
              do_some do_x xfo

              let () = iter print_int print_string
              { o0o=None; xos = [(1,"o");(2,"oo")]; xfo = Some 3; s="example" }
            Your message has been successfully submitted and would be delivered to recipients shortly.