help wanted with recursive types across module boundaries

help wanted with recursive types across module boundaries

[Norman Ramsey]

I'm having trouble breaking a recursion that crosses module
boundaries.

I have a representation of probability distributions.
Ordinarily I would use a monad, declaring type 'a dist, with unit,
bind, and other operations, but I want (among other implementations)
an efficient implementations in terms of sets, so polymorphism is not
indicated.  I therefore have

  module type Dist = sig
    type v (* values *)
    type dist (* probability distribution over values *)
    val unit : v -> dist   
    val bind : dist -> (v -> dist) -> dist
      ... 
  end

Of the values in which I am interested, one kind of value is a
function from values to probability distributions over values.

  module Value = struct
    type 'vdist v
      = Int of int
      | Record of (name * 'vdist v) list
      | Function of ('vdist v -> 'vdist)
  end

Now I want to close the loop.  If I were writing Standard ML, I would
attempt the following:

  module type ValueDist = sig
    include Dist
    type v' = V of dist Value.v
    sharing type v = v'
  end

(I enclose the equivalent Standard ML code below, which compiles.)

I want to write a functor that takes ValueDist as an argument.
How can I do this in OCaml?


Norman

(* type-correct standard ml code follows *)

  signature Dist = sig
    type v (* values *)
    type dist (* probability distribution over values *)
    val unit : v -> dist   
    val bind : dist -> (v -> dist) -> dist
  end

  structure Value = struct
    datatype 'vdist v
      = Int of int
      | Record of (string * 'vdist v) list
      | Function of ('vdist v -> 'vdist)
  end

  signature ValueDist = sig
    include Dist
    datatype v' = V of dist Value.v
    sharing type v = v'
  end

help wanted with recursive types across module boundaries

[Thorsten Ohl]

> If I were writing Standard ML, I would attempt the following:
> 
>   module type ValueDist = sig
>     include Dist
>     type v' = V of dist Value.v
>     sharing type v = v'
>   end

AFAIK, there is no `sharing' keyword in O'Caml, but you should be able
to use the `with' operator instead:

    module type Dist =
      sig
    	type v
    	type dist
      end
    
    module Value =
      struct
    	type name
    	type 'vdist v
    	  = Int of int
    	  | Record of (name * 'vdist v) list
    	  | Function of ('vdist v -> 'vdist)
      end
    
    (* If the implementation were absent, one could not refer
       to Dist.dist below.  Strangely enough, placing Dist in
       a separate dist.mli file (w/o a dist.ml) would work.
       I've never understood the reason for this behavior ... *)
    
    module Dist : Dist =
      struct
    	type v
    	type dist
      end
    
    type vdv = V of Dist.dist Value.v
    
    module type ValueDist =
      sig
    	include Dist
    	type v' = vdv
      end with type v = vdv

At least it compiles and if type equivalence is transitive, it should
do the right thing:
    
    ohl@heplix4:~tmp$ ocamlc -i -c nr.ml
    module type Dist = sig type v and dist end
    module Value :
      sig
	type name
	and 'a v =
	    Int of int
	  | Record of (name * 'a v) list
	  | Function of ('a v -> 'a)
      end
    module Dist : Dist
    type vdv = V of Dist.dist Value.v
    module type ValueDist = sig type v = vdv and dist and v' = vdv end

Cheers,
-Thorsten
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]