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