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

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

Expand Messages
  • 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 1 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 2 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.