Is it possible to use GADTs with default arguments?

A dead simple GADT example:

type _ container =
    Int : int -> int container
  | String : string -> string container
  | Bool : bool -> bool container

let unbox (type t) : t container -> t = function
    Int i -> i
  | String s -> s
  | Bool b -> b

However, when I try to add a default argument to a similar function, it does not compile.

let unbox_default (type t) ?(c:t container=Int 1) (():unit) : t =
  match c with
    Int i -> i
  | String s -> s
  | Bool b -> b
File "lib/test.ml", line 11, characters 43-48:
11 | let unbox_default (type t) ?(c:t container=Int 1) (():unit) : t =
                                                ^^^^^
Error: This expression has type int container
       but an expression was expected of type t container
       Type int is not compatible with type t

Is there a way around this?

Also: polymorphic local type is not the answer.

let unbox_default : type t. ?c:t container -> unit -> t =
  fun ?(c=Int 1) () ->
  match c with
    Int i -> i
  | String s -> s
  | Bool b -> b

this has the same error message.

I don’t think there’s a way. The optional argument desugars to something like

let unbox_default (type t) ~(c:t container option) () =
  let c = match c with Some c -> c | None -> Int 1 (* type error *) in
  ...
1 Like

This almost feels like a bug. Seems like it should be “legal” to annotate a broader output type than what is inferred. Polymorphic variants can do it.

In brief, you cannot have a default type with the standard option type.

When the label layer is removed, your function is equivalent to:

let unbox_default (type t) (c:t container option)  =
  let opt = match c with
    | Some c -> c
    | None -> Int i
  in
  match opt with
  | Int i -> i
  | String s -> s
  | Bool b -> b

which fails with

      but an expression was expected of type t container
      Type int is not compatible with type t

because the default case Int i can only work for int containers.

The problem is thus that the type that we want for unbox_default is not

t container option -> t

but something like

<default:int container; ty:t container> option' -> t

So let’s write such option' type :

type _ option' =
| Nothing : <default:'d; ty:'d> option'
| Just: 'ty -> <default:'d; ty:'ty> option'

With this, we can rewrite the long form of the unbox_default to:

let unbox_default (type t) 
  (c:<default:int container; ty:t container> option'): t  =
  let opt = match c with
    | Just c -> c
    | Nothing -> Int 0
  in
  match opt with
  | Int i -> i
  | String s -> s
  | Bool b -> b

which has the expected behavior. Unfortunately (or not), this GADT variant of the option type is not the one used by optional labels.

3 Likes
<default:int container; ty:t container> option' -> t

I’ve never seen this syntax used in this way before; is this an object type? In order to allow subtyping?

1 Like

I was writing the same thing. I’ve seen object types annotated this way, but I’m not familiar with it from else where. I’d like to see some documentation about it.

It is an object type, but I am using here as a type-level record without any link to subtyping.

OCaml - Objects in OCaml ?

Oh. I think I get it. It’s like how you can use types to pass around information at compile time.

type 'a foo = int
let string_foo : int -> string foo = Fun.id
let char_foo : int -> char foo = Fun.id

It’s just a thing you use for extra info that might be relevant later. (which can also be true of GADT constructor types.)

You’re just using object types to give the type system the info it needs.

1 Like

Wow, it never occurred to me that object types could be used in this way. This seems pretty powerful!

Also, now I’m curious: are there any useful ways of using object subtyping and row polymorphism without involving actual ocaml objects using GADTs?

1 Like

Hopefully @octachron’s answer already gives you some hints, but there is a fundamental issue with your function’s declared type:

module type S = sig
  type 'a container
  val unbox_default : ?c:'a container -> unit -> 'a
end

type bot = { any : 'a. 'a }
let bot (module M : S) : bot = { any = M.unbox_default () }

This type-checks, which means that if you could implement a function of the given type, whatever its implementation (and whatever the container type is), you would break the type system.

As a side-note, @octachron’s trick with object types is equivalent to a version with two distinct type parameters (type ('default, 'ty) option' = ...) but more readable and with easier to understand error messages. It’s unfortunately only possible with GADTs, but if you define types with a bit too many parameters and don’t need variance or injectivity you might want to consider this trick too.

If you mean using objects as a type level record it’s possible with regular adt using type 'a foo = Bla of 'x * 'y option constraint 'a = < x : 'x; y : 'y >, meaning what type < x : 'x; y : 'y > foo = ... would mean if it wasn’t a syntax error.

In the wild coq/plugins/ltac/tacexpr.mli at 3d1668c41b2700cdf59310967b4cc7473a24a4f6 · coq/coq · GitHub

I’m going to be honest: I don’t understand at all why this is true. While I find your and @octachron’s exaples interesting to ponder, I don’t actually understand what they are telling me about the type system. It’s more like a “neat trick” to me at this point, perhaps because I don’t really understand how OCaml’s type system works at a deep level. I just know some stuff works and other stuff doesn’t. Another example of this is polymorphic local type variables. I don’t understand why it’s necessary, only that it necessary is in order to get certain kinds of functions to type-check. I could describe the cases where it is necessary, but not why the compiler “needs” this.

Hmm… I’m not sure if it conveys the idea better, but I’ll break down how the type of the function is interpreted by the compiler to see if it helps understanding why the type itself is problematic.
The type we’re starting from is:

?c:'a container -> unit -> 'a

Let’s first remove the optional argument and replace it with an option, and remove the unit:

'a container option -> 'a

This is a bit simpler and shows the same problem.
One thing that is important is that this type is given to a toplevel binding. Either in a module signature, like in my example, or just by typing the let-binding in your original example. This means that the type variable 'a is interpreted as universally quantified (“for all alpha …”), and the type is actually:

'a . 'a container option -> 'a

Or equivalently, if you prefer local types:

type t. t container option -> t (* Note: this version is not valid syntax in signatures *)

I think it is a bit unfortunate that quantification is not more explicit in OCaml; here are a few more examples where this is felt:

type 'a r = {
  id1 : 'a -> 'a; (* monomorphic function, whose type is linked to the type parameter *)
  id2 : 'a. 'a -> 'a; (* polymorphic function, independent of the type parameter *)
}
module M = struct
  let g : 'a -> 'a = fun x -> x (* variable bound at the definition of g, and generalized *)
  let v = (g 0, g false) (* works, as g is polymorphic *)
end
let v =
  let g : 'a -> 'a = fun x -> x in (* variable bound at the definition of v, not generalizable *)
  (g 0, g false) (* compilation error, as g is not polymorphic *)
let v =
  let g : 'a. 'a -> 'a = fun x -> x in (* Explicit polymorphic annotation *)
  (g 0, g false) (* works, as g is polymorphic *)

Anyway, back to our initial problem.
Since its type is polymorphic, you can use the function with any instantiation of the type variable. So the following are all valid:

let f : type t. t container option -> t = ...
let f_int : int container option -> int = f
let f_bool : bool container option -> bool = f
let f_string : string container option -> string = f

Something already looks fishy: the bool and string versions return booleans and strings, even though you expected the default case to return an integer. But the following is also allowed, and more obviously wrong:

let f_float : float container option -> float = f

You don’t expect f_float to actually return a floating point number, and you don’t want your function to raise an exception or loop infinitely, so the only hope is that it is impossible to actually create a value of type float container option. If you don’t have the option, it works: the GADT constraints actually ensure that such inputs don’t exist. You can try it with the unbox function:

let unbox : type t. t container -> t = ...
let unbox_float : float container -> float = unbox

It compiles, but you will never be able to get a float out of unbox_float because you cannot create a value of type float container to pass to it.

But with the option, it doesn’t work anymore: None can have type t option for any t, including types for which no value exists like float container. You cannot constraint the option type to only allow None at some specific types, which is what your initial example seems to be trying to do (when given None, you function returns an integer, so it means that you should only allow None at type int container option).
And here we link back to @octachron’s answer: he showed you how to define your own option-like type where you can put restrictions on the type of None, and with these restrictions your code becomes correct (although as he said, you cannot overload the syntax for optional arguments with custom option types so it’s more cumbersome to use).
If you wanted something a bit less fancy, you could have defined the custom option type like this:

type _ container_option =
| None : int container_option
| Some : 'a container -> 'a container_option
let unbox_default (type t) (c: t container_option): t  =
  let opt : t container = match c with
    | None -> Int 1
    | Some c -> c
  in
  match opt with
  | Int i -> i
  | String s -> s
  | Bool b -> b

Typing for optional arguments is done using the pre-defined option type and constructors, not the option type or Some/None constructors currently in scope, so overriding the constructors and the type still doesn’t allow you to use optional argument syntax.

3 Likes

I think this makes sense to me. Thanks for going through it in more detail.

I think I understand why you can’t implement 't container option -> 't; because if It’s None, there is no 't not even an instance to supply the 't.

I guess the thing I don’t really get is why there isn’t a heuristic to “make it work” with default arguments, since it can be guaranteed that there will always be something there (in the end) that supplies a type parameter.

I realize this is because the default arguments expand to option types, but it seems like it would be possible to patch the compiler to see the default argument pattern and accept that it will work in the end.

Optional arguments in OCaml do not require a default (not requiring it is sometimes very useful), and are not distinguished from default arguments at the type level.

You would at least need to change the syntax for optional argument types to specify the type of the default case.
For your example, instead of unbox_default : ?c:'a container -> unit -> 'a, this would be something like unbox_default : ?<int container>c:'a container -> unit -> 'a. Then at the call site, if the argument is missing the type-checker would need to resolve the additional constraint so that the final type is correctly inferred as int (maybe this can be done with unification, I’m not completely sure).

Note that you could also write a ppx to expand call sites with the default argument if it is missing, avoiding the need for the option wrapper, but you get into the issue of making sure that you always see the definition and all the call sites together (plus some scope issues, as the default expression might use constructors that are internal and not exported at the call site).

Finally, you should also be able to do that:

let unbox (type t) : t container -> t = function
    Int i -> i
  | String s -> s
  | Bool b -> b

let unbox_default ?(c:int container=Int 1) (():unit) : int =
  unbox c

The type has been restricted to int, and so it is safe.

This can be done with unification by elaborating to a GADT-enhanced option type rather than the standard one (see an old prototype). But then you have GADTs introduced by code elaboration, and I never had the time to investigate how horrible the error messages end up.

1 Like