13657Re: "ocaml_beginners":: What is the best way to code this data structure?
- Nov 1, 2012On Thu, Nov 1, 2012 at 5:22 PM, Max Hayden Chiz <max.chiz@...> wrote:
> **Thanks, nice example of polymorphic recursion!
> On Thu, Nov 1, 2012 at 3:04 AM, Gabriel Scherer
> > 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
> > =
> > 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 thatfirst. The unfortunate thing is you will not be able to neither "just not
> I can pass the right do functions to iter.
> The type system will keep reminding you which kind of elements comes
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 beThis extra step remembers which kind of elements comes first, so that some
> 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)
> Is that right or is there a way to do away with this extra step?
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]
- << Previous post in topic Next post in topic >>