How to write an fmap method for an object?

Learning
1

I rarely use objects, and although I think I understand the basic concepts, I struggle defining recursive object types.

For example if I want to replace this module with an object:

  module Foo = struct
    type 'a t = 'a option
    let is_none = function | None -> true | Some _ -> false
    let fmap f = function
      | None -> None
      | Some v -> Some (f v)
  end

My first attempt compiles, but the inferred type is not as general as I would like:

  class ['v] foo (v:'v option) = object(self:'self)
    method is_none = match v with
      | None -> true
      | Some _ -> false
    method fmap: ('v -> 'b) -> 'b foo = fun f ->    
      let v = match v with
      | None -> None
      | Some v -> Some (f v) in
      new foo v
  end;;

class ['v] foo :
  'v option ->
  object method fmap : ('v -> 'v) -> 'v foo method is_none : bool end

I tried adding an annotation, but there is a problem with scoping:

class ['v] foo (v:'v option) = object(self)
  method is_none = match v with
    | None -> true
    | Some _ -> false
  method fmap: 'b. ('v -> 'b) -> 'b foo = fun f ->
    let v = match v with
    | None -> None
    | Some v -> Some (f v) in
    new foo v
end
;;
Line 5, characters 15-39:
Error: The universal type variable 'b cannot be generalized:
       it escapes its scope.

Trying to define a type failed too:

type 'v foo = < fmap: 'b. ('v -> 'b) -> 'b foo >;;
Line 1, characters 0-48:
Error: In the definition of foo, type 'b foo should be 'v foo

Class type too:

class type ['v] foo = object
  method fmap: 'b. ('v -> 'b) -> 'b foo
end
;;
Line 2, characters 15-39:
Error: The universal type variable 'b cannot be generalized:
       it escapes its scope

What am I missing?

2

Oleg Kiselyov talks about this problem here: http://okmij.org/ftp/Computation/extra-polymorphism.html#irregular

You can’t do what you want with objects, but he provides a work around that uses an auxiliary type.

2 Likes
3

Thank you, that described my problem exactly!