F#un with Phantom Types

With Halloween tomorrow, now is the perfect time to take a look at phantom types in F#.  So what are phantom types?  Think of them as a way to embed a constraint into the type system of a language.  Here’s a great example of using them in OCaml.  And what you can do in OCaml you can do in F# right?

 

Trick or Treat?

 

The first thing we want to do is break out the essence of what makes a phantom type possible to see if we can do them in F#.  We’ll simplify the OCaml into the following.

 

module DepList:

sig

 type (’a,’length) t

 val toList:(’a,’length) t -> ‘a list

end

 =

struct

 type (’a,’length) t=’a list

 let toList l = l

end

 

All we’re left with is a typedef for a list that takes an additional type parameter, and an identity function that transforms our multi type parameter list back into a single type parameter list.  Simple enough, if not rather difficult to say.

 

 

module DepList

     type (’a,’length) t

     val toList:(’a,’length) t -> ‘a list

 

module DepList

type (’a,’length) t=’a list

let toList l = l

 

F# does not allow you to combine signatures and implementations in the same file like OCaml.  The signature must be defined in a signature file with the fsi extension and the implementation must be defined in a file with the fs extension.  The first problem we run into with the above code is a warning that multi-argument generic type instantiations are for OCaml compatibility.  Let’s do some quick rearranging to make our type more F# like.

 

module DepList

     type Phantom<’a,’length>

     val toList : Phantom<’a,’length> -> ‘a list

 

module DepList

type Phantom<’a,’length> =  ‘a list

let toList l = l

 

Unfortunately, the above code doesn’t compile.  The compiler plays it’s first trick of the evening.

 

The type definitions in the signature and implementation are not compatible because an abbreviation is being hidden by a signature. The abbreviation must be visible to other .NET languages.

 

Unlike OCaml, F# does not allow you to abstract type equations.

 

type Phantom<’a,’length>

type Phantom<’a,’length> = ‘a list

 

must become

 

type Phantom<’a,’length>

type Phantom<’a,’length> = Phantom of ‘a list

 

or

 

type Phantom<’a,’length> = ‘a list

type Phantom<’a,’length> = ‘a list

 

This second way gives a rather bizarre warning about type erasure.  Let’s stick to the first.  These type definitions are the key to phantom types.  All we’ve done is create a typedef for a list with an additional parameter.  The length parameter is the real phantom type.  It’s an extra parameter whose sole purpose is to act as a constraint on our list.  So does F# allow us to create typedefs with an extra parameter hanging around?

 

Module ‘DepList’ contains  val toList<’a> : ‘a -> ‘a but its signature specifies  val toList<’a,’length> : Phantom<’a,’length> -> ‘a list The respective type parameter counts differ.

 

Nope.  The tricks on us this Halloween.

 

val toList : Phantom<’a,’length> -> ‘a list

let toList l = l

 

Despite out best efforts, the compiler sees right through the length parameter.  There doesn’t seem to be anyway to drop the extra parameter.  When we construct our list we’ll get the following type.

 

//val l : Phantom<int,’a>

let l = Phantom [1;2;3]

 

Our list really is a list under the covers.  Can’t we somehow get it back?   Of course we can.  We’ve spent the last few blogs looking at pattern matching.

 

module DepList

type Phantom<’a,’length> = Phantom of ‘a list

let toList (l : Phantom<’a,’length>) =

    match l with

    | Phantom l -> l

 

Looks like we may be having treats this Halloweeen after all.