Sorry, an error occurred while loading the content.

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

Expand Messages
• 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