Is there a way to make this continuation passing with codata example work in F#?

Question

type Interpreter<'a> =
| RegularInterpreter of (int -> 'a)
| StringInterpreter of (string -> 'a)

let add<'a> (x: 'a) (y: 'a) (in_: Interpreter<'a>): 'a = 
    match in_ with
    | RegularInterpreter r -> 
        x+y |> r
    | StringInterpreter r -> 
        sprintf "(%s + %s)" x y |> r

The error message of it not being able to resolve 'a at compile time is pretty clear to me. I am guessing that the answer to the question of whether it is possible to make the above work is no, short of adding functions directly into the datatype. But then I might as well use an interface, or get rid of generic parameters entirely.

Edit: Mark's reply does in fact do what I asked, but let me extend the question as I did not explain it adequately. What I am trying to do is do with the technique above is imitate what what was done in this post. The motivation for this is to avoid inlined functions as they have poor composability - they can't be passed as lambdas without having their generic arguments specialized.

I was hoping that I might be able to work around it by passing an union type with a generic argument into a closure, but...

type Interpreter<'a> =
| RegularInterpreter of (int -> 'a)
| StringInterpreter of (string -> 'a)

let val_ x in_ =
    match in_ with
    | RegularInterpreter r -> r x
    | StringInterpreter r -> r (string x)

let inline add x y in_ = 
    match in_ with
    | RegularInterpreter r -> 
        x in_ + y in_ |> r
    | StringInterpreter r -> 
        sprintf "(%A + %A)" (x in_) (y in_) |> r

let inline mult x y in_ = 
    match in_ with
    | RegularInterpreter r -> 
        x in_ * y in_ |> r
    | StringInterpreter r -> 
        sprintf "(%A * %A)" (x in_) (y in_) |> r

let inline r2 in_ = add (val_ 1) (val_ 3) in_

r2 (RegularInterpreter id)
r2 (StringInterpreter id) // Type error.

This last line gives a type error. Is there a way around this? Though I'd prefer the functions to not be inlined due to the limits they place on composability.

Answer 1

The compiler ends up defaulting to int, and the kind of polymorphism you want is difficult to achieve in F#. This article articulates the point.

Perhaps, you could work the dark arts using FSharp.Interop.Dynamic but you lose compile time checking which sort of defeats the point.

Answer 2

I've come to the conclusion that what I am trying to is impossible. I had a hunch that it was already, but the proof is in the following:

let vale (x,_,_) = x
let adde (_,x,_) = x
let multe (_,_,x) = x

let val_ x d =
    let f = vale d
    f x

let add x y d =
    let f = adde d
    f (x d) (y d)

let mult x y d =
    let f = multe d
    f (x d) (y d)

let in_1 =
    let val_ (x: int) = x
    let add x y = x+y
    let mult x y = x*y
    val_,add,mult

let in_2 =
    let val_ (x: int) = string x
    let add x y = sprintf "(%s + %s)" x y
    let mult x y = sprintf "(%s * %s)" x y
    val_,add,mult

let r2 d = add (val_ 1) (val_ 3) d

//let test x = x in_1, x in_2 // Type error.

let a2 = r2 in_1 // Works
let b2 = r2 in_2 // Works

The reasoning goes that if it cannot be done with plain functions passed as arguments, then it definitely won't be possible with interfaces, records, discriminated unions or any other scheme. The standard functions are more generic than any of the above, and if they cannot do it then this is a fundamental limitation of the language.

It is not the lack of HKTs that make the code ungeneric, but something as simple as this. In fact, going by the Finally Tagless paper linked to in the Reddit post, Haskell has the same problem with needing to duplicate interpreters without the impredicative types extension - though I've looked around and it seem that impredicative types will be removed in the future as the extension is difficult to maintain.

Nevertheless, I do hope this is only a current limitation of F#. If the language was dynamic, the code segment above would in fact run correctly.

Answer 3

Unfortunately, it's not completely clear to me what you're trying to do. However, it seems likely that it's possible by creating an interface with a generic method. For example, here's how you could get the code from your answer to work:

type I = abstract Apply : ((int -> 'a) * ('a -> 'a -> 'a) * ('a -> 'a -> 'a)) -> 'a

//let test x = x in_1, x in_2 // Type error.
let test (i:I) = i.Apply in_1, i.Apply in_2

let r2' = { new I with member __.Apply d = add (val_ 1) (val_ 3) d }
test r2' // no problem

If you want to use a value (e.g. a function input) generically, then in most cases the cleanest way is to create an interface with a generic method whose signature expresses the required polymorphism.

Answer 4

Remove the type annotations:

let inline add x y in_ = 
    match in_ with
    | RegularInterpreter r -> 
        x + y |> r
    | StringInterpreter r -> 
        sprintf "(%A + %A)" x y |> r

You'll also need to make a few other changes, which I've also incorporated above:

• Change the format specifiers used with sprintf to something more generic. When you use %s, you're saying that the argument for that placeholder must be a string, so the compiler would infer x and y to be string values.
• Add the inline keyword.

With these changes, the inferred type of add is now:

x: ^a -> y: ^b -> in_:Interpreter<'c> -> 'c
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b -> int)

You'll notice that it works for any type where + is defined as turning the input arguments into int. In practice, that's probably going to mean only int itself, unless you define a custom operator.

FSI smoke tests:

> add 3 2 (RegularInterpreter id);;
val it : int = 5
> add 2 3 (StringInterpreter (fun _ -> 42));;
val it : int = 42