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

9075Re: "ocaml_beginners"::[] Circular dependencies between modules

Expand Messages
  • Jon Harrop
    Dec 1, 2007
    • 0 Attachment
      On Saturday 01 December 2007 10:40, Fabrice Marchant wrote:
      > Thanks Jon !
      >
      > > > There are workarounds ( I've even written an ugly one in order not to
      > > > let my build stuck ) but I hope to learn what would be a clean way to
      > > > perform this.
      > >
      > > Yes, you need to break the cyclic dependence by parameterizing one
      > > definition over another.
      >
      > Please Jon, could you develop a bit more on this ?
      > I'm unable to see what you mean here.

      Sure. Consider a pair of mutually recursive functions:

      # let rec even ?(xs=[]) ?(ys=[]) = function
      | [] -> xs, ys
      | h::t -> odd ~xs:(h::xs) ~ys t
      and odd ?(xs=[]) ?(ys=[]) = function
      | [] -> xs, ys
      | h::t -> even ~xs ~ys:(h::ys) t;;
      # even [0;1;2;3;4;5];;
      - : int list * int list = ([4; 2; 0], [5; 3; 1])

      We want to keep them in separate modules and, consequently, we must break
      their cyclic dependency. To do this, you just parameterize "even" over "odd"
      and vice-versa:

      # let rec even odd xs ys = function
      | [] -> xs, ys
      | h::t -> odd (h::xs) ys t;;
      val even :
      ('a list -> 'b -> 'a list -> 'a list * 'b) ->
      'a list -> 'b -> 'a list -> 'a list * 'b = <fun>
      # let odd even xs ys = function
      | [] -> xs, ys
      | h::t -> even xs (h::ys) t;;
      val odd :
      ('a -> 'b list -> 'b list -> 'a * 'b list) ->
      'a -> 'b list -> 'b list -> 'a * 'b list = <fun>

      Some people refer to this as "untying the recursive knot". Now, how do we use
      these? Well, we just tie the knot again in a module that depends upon both:

      # let rec even' xs = even odd' xs and odd' xs = odd even' xs in
      even' [] [] [0;1;2;3;4;5];;
      - : int list * int list = ([4; 2; 0], [5; 3; 1])

      You can do exactly the same thing with types:

      type a = A of b
      and b = B of a;;

      becomes:

      type 'b a = A of 'b;;
      type 'a b = B of 'a;;

      and so on.

      --
      Dr Jon D Harrop, Flying Frog Consultancy Ltd.
      http://www.ffconsultancy.com/products/?e
    • Show all 15 messages in this topic