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

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

Expand Messages
  • Max Hayden Chiz
    Nov 1, 2012
      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]
    • Show all 12 messages in this topic