Is it possible to "anonymize" the type parameter in a record field definition?

Learning
1

Very basic question here. I wasn’t sure how to title the post because I’m not sure what the name is for the syntax I’m looking for.

I’d like to create a parameterized type that contains a reference to another of the same type, but regardless of its type parameter, to provide access to the non-parameterized fields.

Something like this:

type 'a person = { 
    name: string;
    friends: '_ person list;
  };;

or

type 'a person = { 
    name: string;
    friends: 'b person list;
  };;

neither of which compile.

An example of use is a function determining if one person is another person’s friend, where the type parameter is irrelevant.

let is_friend person friend = 
  person.friends
  |> List.find ~f:(fun p -> String.equal p.name friend.name) 
  |> Option.is_some

I know functions are defined that ignore the type parameter all the time, like List.length. Is it possible to define a type’s field like this? How is it done?

2

Yes, you can use a simple GADT to introduce an “existential type” to hide that type parameter. It can be written like this:

type 'a person = {
    name: string;
    friends: any_person list;
  }

and any_person = Any : _ person -> any_person

let is_friend person friend =
  person.friends
  |> List.find ~f:(fun (Any p) -> String.equal p.name friend.name)
3 Likes
3

An alternative without GADTs:

type 'a person = {
  name: string;
  friends: vertex_view list;
  other:'a;
}
and vertex_view = { 
  name: unit -> string; 
  friends: unit -> vertex_view list
}
let view x: vertex_view = { 
  name= (fun () -> x.name); 
  friends = (fun () -> x.friends)
}
let friends l = List.map view l 
let a = { name = "A"; friends = []; other = "" }
let b = { name="B"; friends = friends [a]; other = 1 }
let is_friend person friend_name =
  List.exists 
  (fun (f':vertex_view) -> friend_name =  f'.name ()) 
  person.friends
1 Like
4

Thank you. Is your solution missing anything? When I paste it into emacs merlin complains that the label name is defined in both person and vertex_view.

5

Thanks very much! Both this and the solution without the GADT are illuminating, but this one seems to make the intention more explicit - it directly says it’s creating a type that hides the type parameter, which to me is clearer.

6

Can I ask what the purpose of the “wrapper function” is here? If I remove it like below everything seems to still work:

...
and vertex_view = {
  name: string;
  friends: vertex_view list
}

let view x: vertex_view = {
  name = x.name;
  friends = x.friends
}

Is it just that in a more “real-world” example you would probably want something other than a simple “same value” or is there some subtlety I’m missing?

Thanks

7

This is a ignorable warning, which is disabled by default by the compiler since OCaml 4.10.0 .

The root issue is the immutable friends list in the definition of person. Such definition requires all members of a cycle to be simultaneously defined in a mutually recursive definition:


let rec a: _ person  = {
  name = "A";
  friends = [ { friends = (fun () -> b.friends); name = (fun () -> b.name) }];
  other = ()
  }
and b = {
  name = "B";
  friends = [
    { friends = (fun () -> a.friends); name = (fun () -> a.name) }
  ];
  other = 1
}

and this works (barely) because the access to b in the friends field of a are guarded under
(fun () -> ...).

1 Like
8

Ah! that makes sense - I only tried out a simple graph A=>B and didn’t consider cycles.

Thanks