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