this construct causes code to be less generic... when applied to phantom type

Question

I am trying to implement a DSL in F# for a small language. Unfortunately the compiler stops me dead in my tracks when I attempt to constrain nodes to hold additional type information (via phantom types).

The following lines of code illustrate the issue:

type Expr<'a> =
| Int of int
| Eq  of Expr<int> * Expr<int>
| Not of Expr<bool>

let rec to_string (expr: Expr<'a>) = 
  match expr with
  | Int(n)   -> string n
  | Eq(x, y) -> sprintf "%s == %s" (to_string x) (to_string y)
  | Not(b)   -> sprintf "!%s" (to_string b)

According to the compiler the construct to_string x issues the following warning:

construct causes code to be less generic than indicated by the type annotations. The type variable 'a has been constrained to be type 'int'.

Following that, on the next line, the construct to_string b issues this error:

Type mismatch. Expecting a Expr<int> but given a Expr<bool> The type int does not match the type bool

I can't seem to find any way to circumvent this behavior, and in fact I can't find the cause this code being less generic than what I had expected. If possible I would prefer a solution that doesn't entirely abandon the phantom types.

Am I doing something fundamentally wrong? Could this be a compiler bug?

Answer 1

You need to make the to_string function generic:

let rec to_string<'a> (expr:Expr<'a>) : string = 
  match expr with
  | Int(n)   -> string n
  | Eq(x, y) -> sprintf "%s == %s" (to_string x) (to_string y)
  | Not(b)   -> sprintf "!%s" (to_string b)

The type parameter will be inferred when you call the function

Not (Eq (Int 1, Int 2))
|> to_string