[Caml-list] module type constraints problem

[Warren Harris <warren@kontiki.com>]

[-- Attachment #1: Type: text/plain, Size: 2446 bytes --]

Hi. I'm wondering if someone on this mailing list can help me with a 
module type problem. What I would like to achieve is an iteration 
abstraction (module) that is parameterized by the node and element type 
of the data to be iterated over. I want to implement this abstraction 
for different data types including lists, and a language expression type.

In the list case, the element type is abstract ('a), and the node type 
is 'a list.

In the expr case, the element type is expr (the exprs themselves, not 
some sub-element of the exprs), and the node type is also expr.

Here's my module type:

    module type Iter =
    sig
      type 'a t
      val iter : ('a -> unit) -> 'a t -> unit
    end

and here's the list implementation (works great):

    module ListIter : Iter =
    struct
      type 'a t = 'a list
      let iter f l = List.iter f l
    end

Here's a simlified version of my expr type:

    type expr =
        Expr of int * expr * expr
      | Int of int
      | Unit

But this implementation of the Iter module won't type check:

    module ExprIter : Iter =
    struct
      type 'a t = expr
      let rec iter f e =
        f e;
        match e with
            Expr(i, a, b) -> iter f a; iter f b
          | e -> ()
    end

    Signature mismatch:
    Modules do not match:
      sig type 'a t = expr val iter : (expr -> 'a) -> expr -> unit end
    is not included in
      Iter
    Values do not match:
      val iter : (expr -> 'a) -> expr -> unit
    is not included in
      val iter : ('a -> unit) -> 'a t -> unit

Adding explicit constraints to the parameters of the iter function don't 
help either:

    module ExprIter : Iter =
    struct
      type 'a t = expr
      let rec iter (f:'a -> unit) (e:'a t) =
        f e;
        match e with
            Expr(i, a, b) -> iter f a; iter f b
          | e -> ()
    end

    Signature mismatch:
    Modules do not match:
      sig type 'a t = expr val iter : (('a t as 'a) -> unit) -> 'a ->
    unit end
    is not included in
      Iter
    Values do not match:
      val iter : (('a t as 'a) -> unit) -> 'a -> unit
    is not included in
      val iter : ('a -> unit) -> 'a t -> unit

Is there some additional way to constrain this problem such that the 
type checker will accept it? If you look closely, 'a t = 'a = expr yet 
the type checker is failing to deduce the equality of the two iter 
function types.

Any help would be greatly appreciated,

Warren

[-- Attachment #2: Type: text/html, Size: 3192 bytes --]