[Caml-list] sum types with objects

[Caml-list] sum types with objects

[Tom Hirschowitz]

Hi all,

when trying to implement lists with objects and classes, I run into
the following issue.

The idea is to define a class type list, parameterized over the type
'a of elements, and containing the methods is_nil, hd, tl, map. Then,
I planned to define two classes nil and cons for building objects of
type list.

The problem arises during the typing of list:

# class type ['a] list = object
  method is_nil : bool
    method hd : 'a
    method tl : 'a list
    method map : ('a -> 'b) -> 'b list
  end
    ;;
class type ['a] list =
  object
    method hd : 'a
    method is_nil : bool
    method map : ('a -> 'a) -> 'a list
    method tl : 'a list
  end

The method map has type ('a -> 'a) -> 'a list, which is not what I
want.  Trying to explicitely quantify 'b is also wrong, because 'b
escapes its scope.

Does someone know how to make this work?

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

Re: [Caml-list] sum types with objects

[Didier Remy]

Tom Hirschowitz <Tom.Hirschowitz@ens-lyon.fr> writes:

> when trying to implement lists with objects and classes, I run into
> the following issue.
> 
> The idea is to define a class type list, parameterized over the type
> 'a of elements, and containing the methods is_nil, hd, tl, map. Then,
> I planned to define two classes nil and cons for building objects of
> type list.

See polymorphic methods in the manual. 
http://caml.inria.fr/ocaml/htmlman/manual005.html#ss:polymorphic-methods

Still, you should use fold and not map:

    class type ['a] list = object
      method is_nil : bool
      method hd : 'a
      method tl : 'a list
      method fold  : 'b. ('a -> 'b -> 'b) -> 'b -> 'b
    end;;

    exception Nil;;
    class ['a] nil = object (self : 'a #list)
      method is_nil = true
      method hd = raise Nil
      method tl = raise Nil
      method fold f x = x
    end;;

    class ['a] cons h t = object (self : 'a #list)
      method is_nil = false
      method hd = h
      method tl : 'a list = t
      method fold f x = f self#hd (self#tl#fold f x)
    end;;

Otherwise, your are trying to define a type abbreviation 

    type ('a, ...) #list = 
         < hd : 'a
           tl : 'a list
           map : 'b. ('a -> 'b) -> ('b) list; ... >

    and 'b list = ('b, <>) list

which is not allowed because the parameter of list in the body is not the
same as the one in the declaration. Type inference will enforce 'b = 'a, 
which is not what you want.

This is not just a matter of typechecking, though.  In particular, 
if you had in mind an implementation of class cons of the form 

     class cons h t = 
       ...
       method map f = new cons (f self#hd) (self#tl#map f)
     end;;

you would then have problems inheriting, since the constructor "new cons" is
here the one of the class "cons" beeing defined and not the one of a
subclass. Hence, you would also need to abstract cons over the constructor
function of the subclass of cons beeing considered, which becomes closer to
(but still less general than) what fold actually does.

        Didier

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