[Caml-list] module type constraints problem

[Caml-list] module type constraints problem

[Warren Harris]

[-- 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 --]

Re: [Caml-list] module type constraints problem

[brogoff]

Hi, 

Here's a hint; Your element type, 'a, is wrong. Try something like this:

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

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

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

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

-- Brian

On Wed, 28 May 2003, Warren Harris wrote:

> 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
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners