Polymorphic Return Types for F#?

We used a good old fashioned subtyping and a dash of parametric polymorphism to write an eval function capable of returning different types.  But surely we gave up too easily on polymorphic return types in F#?  I assure you we gave them the ol’ college try.

 

Polymorphic Return Types Take 1

 

Let’s start with a pretty simple data constructor that constructs two different types.

 

type Term =

    | Int of int

    | Char of char

 

Now we write a rather straightforward eval function to evaluate our terms.  For instance,

 

// Term -> int

let eval t =

    match t with

    | Int i -> i

    //the expression has type char but here is used with type int

    | Char c -> c

 

But because our first match returns an integer our second must also return a char.

 

Polymorphic Return Types Take 2

 

Just because the compiler doesn’t like what you’re trying to do doesn’t mean it isn’t right.  Let’s take a different tact.

 

// Term -> obj

let eval t =

    match t with

    | Int i -> i :> obj

    | Char c -> c :> obj

 

let i = eval (Int 1)

let c = eval (Char ‘c’)

printfn “%A” i

printfn “%A” c

 

So we sacrifice our type safety to get a couple of values printed to the console.  Not what we had in mind.  We want the type system to guide us instead of forcing us to throw it out the window.

 

Polymorphic Return Types Take 3

 

So if we can’t return a different type and we don’t want to lose our type safety, let’s try returning all possible types.

 

// Term -> Choice<int,char>

let eval t =

    match t with

    | Int i -> Choice2_1 i

    | Char c -> Choice2_2 c

 

let i = eval (Int 1)

let c = eval (Char ‘c’)

 

So our eval function compiles and returns a different choice for each constructor.  All we have to do now is extract the value out of the choice and were done.

 

// Term -> Choice<’a,’a>

let extract choice =

    match choice with

    | Choice2_1 i -> i

    | Choice2_2 c -> c

// expecting a Choice<int,int> but given a Choice<int,char>

let i = extract (eval (Int 1))

 

And if we annotate the choice function we’ve just reinvented our original problem.

 

// Term -> Choice<int,char> -> int

let extract_int_char (choice : Choice<int,char>) =

    match choice with

    | Choice2_1 i -> i

    //the expression has type char but here is used with type int

    | Choice2_2 c -> c

 

Polymorphic Return Types Take 4

 

Let’s start with a function that does work.

 

// Term -> unit

let display t =

    match t with

    | Int i -> printfn “%A” i

    | Char c -> printfn “%A” c

 

Now can’t we somehow lift the variables out of the function without changing the return type?  Something along the lines of. 

 

// Term -> ‘a ref -> unit

let eval t r =

    match t with

    | Int i -> r := i

    //the expression has type char but here is used with type int

    | Char c -> r := c

 

Only to be thwarted again and all we’re left with to get our values out of eval function is the following monstrosity.

 

// Term -> int ref -> char ref -> unit

let eval t ri rc =

    match t with

    | Int i -> ri := i

    | Char c -> rc := c

 

let ri = ref 0

let rc = ref ‘a’

let ie = eval (Int 1)

let u1 = eval (Int 1) ri rc

let i = !ri

let u2 = eval (Char ‘c’) ri rc

let c = !rc

printfn “%A” i

printfn “%A” c

 

Eat your heart out Perl.  We’ve got a new write once kid on the block.