Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
circular types?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2000-10-22 (19:41)
From: Brian Rogoff <bpr@b...>
Subject: Re: circular types?
On Fri, 20 Oct 2000, Chris Hecker wrote:
> >It's exactly similar to value definitions: put a ``and'' between the
> >two recursive definitions.
> >type foo = B of bar
> >and bar = F of foo
> Ah, thanks!  Is there any way to do it without the "and"?  In other
> what if I want to do this but the types are defined "far away" from each 
> other in the source.  The "and" solution works, but I'm looking for 
> something like forward declarations from C++:
> class foo;
> class bar;
> class foo { bar *Bar; };
> // ...lots of stuff...
> class bar { foo *Foo; };

Nope, no forwards in Ocaml. At some point, you'll have to tie the recursive 
knot with an "and". If the problem you're having is that "far away" means 
"in different modules" then you bump into the lack of recursive modules, 
IMO the biggest PITA with ML style modules. This hurts most in a situation 
where you want something like the Composite pattern with modules  

type composite = { data : string ; children : CompositeSet.t }
and module CompositeSet = 
  Set.Make( struct 
              type t = composite 
              let compare c1 c2  = 
            end )

The first choice, which you don't like, is to put the mutually recursive
types into the same module. This would entail copying all of the source for
Set.Make into the module where you're defining the Composite, and using
"and" to tie the recursion together. I agree this is a poor workaround.

Another choice, which I saw on caml-list in a post from Benoit deBoursetty, 
is to make polymorphic versions of the Set functor by grab-and-hack on the
source of Set, and use the polymorphism to move the recursive dependence out 
of lift the module. So you make a 

module type PolyOrderedType =
    type 'a t
    val compare: 'a t -> 'a t -> int

type 'a composite_fwd = { data : string ; forward : 'a };;

module OrderedComposites =
    type 'a t = 'a composite_fwd
    let compare cf1 cf2 = (String.length (String.length 

module CompositeSet = PolySet.Make(OrderedComposites);;

and given these polymorphic sets we can untie the mutual recursion with an 
"and" as follows 

type children = { children : composite CompositeSet.t }
and  composite = children composite_fwd;;

This is better, but involves an unpleasant extra level of indirection. You
can find the polymorphic sets at

if this technique looks useful.

If the entities involved in the module spanning mutual recursion are
classes, and you *absolutely-don't-want-to-put-them-in-the-same-module*
you can create a dummy module in which the dependent classes are linked
and inherit from that. That moves the mutual recursion but doesn't break
it; there is no way I know of to break it short of doing a downcast or
narrowing-conversion on the classes, which is illegal in Ocaml. 

Here is a silly example; starting with these impossible signatures

module type DoctorType = 
    class c : 
	method treat_patient : PatientType.c 
	method bill_patient : PatientType.c 
  end ;;

module type PatientType = 
    class c : 
	method visit_doctor : DoctorType.c 
	method pay_doctor : DoctorType.c 
  end ;;

we add a parent module which expresses an interface dependency and write
the signatures in terms of that. 

module Forwards = 
    class virtual patient_intf = 
	method virtual visit_doctor : doctor_intf  
	method virtual pay_doctor :   doctor_intf
    and virtual doctor_intf = 
	method virtual treat_patient : patient_intf
        method virtual bill_patient  : patient_intf
  end ;;

module type DoctorType = 
    class c : 
	method treat_patient : Forwards.patient_intf
	method bill_patient : Forwards.patient_intf
  end ;;

module type PatientType = 
    class c : 
	method visit_doctor : Forwards.doctor_intf
	method pay_doctor : Forwards.doctor_intf
  end ;;

-- Brian