There are a few issues here. First of all, you don't really want to parameterize your Tree type by the second parameter 'b - if it's a function call, you just want to ensure that there's some type 'b for which the second case is a pair of a 'b Tree and a function 'b -> 'a. Ideally, your code would look something like this:

1
2
3
4

type 'a Tree=
| Const of 'a
| FuncCall of exists 'b. 'b Tree * ('b -> 'a)

where the "exists" bit is made up syntax for an existential type. Unfortunately, since F# doesn't support existential types, you'll have to encode the existential type using other F# features. There is a well-known pattern for doing this, but it requires a total of 3 types (and they must be mutually recursive because your Tree type is recursive):

1
2
3
4
5
6
7
8

type 'a Tree =
| Const of 'a
| FuncCall of 'a ExistsFunc
and 'a ExistsFunc = (* exists 'b. 'b Tree * ('b -> 'a) *)
  abstract member Apply<'t> : FunUser<'a,'t> -> 't
and FunUser<'a,'t> = (* forall 'b. 'b Tree * ('b -> 'a) -> 't *)
  abstract member Use<'b> : 'b Tree * ('b -> 'a) -> 't

Now that you've defined this type, you can define functions to do things like evaluation. Unfortunately, you'll find that defining recursive functions on your type is not straightforward because the recursive call uses a different type ('b Tree, for some 'b) than your initial call ('a Tree). You can't define functions that do this kind of generic recursion using let bindings in F# - you need to define a type with members having explicit generic type signatures. Therefore, your eval function ends up looking like this:

1
2
3
4
5
6
7

type Eval =
  static member eval<'a> (e:'a Tree) : 'a =
    match e with
    | Const a -> a
    | FuncCall u -> 
        u.Apply { new FunUser<'a,'a> with member x.Use (inp,f) = f (Eval.eval inp) }

You can also write a simple function to create FuncCall cases based on a (Tree, function) pair - again there is a well known pattern for defining these functions:

1
2

let pack x = { new ExistsFunc<_> with member this.Apply f = f.Use x }

Now your example can be written out like so:

1
2
3
4
5
6
7
8

let ex_f x = any_to_string (x*x)
let ex_f2 s = "res: " + s
let c = Const(3)
let fc = FuncCall (pack (c, ex_f))
let fc2 = FuncCall (pack (fc, ex_f2))

let result = Eval.eval fc2

Obviously, this is all a bit more verbose than one would like, but it is possible.