If I change the Visitor interface a little bit:

public interface IExpressionVisitor<T>

{

T Visit(BinaryExp expression);

T Visit(Exp expression);

}

Then I can do it:

type FSExpression =

| Var of string

| Add of FSExpression * FSExpression

let rec visitor =

{ new IExpressionVisitor<FSExpression> with

member v.Visit(x : BinaryExp ) =

let left = x.Left.Accept visitor

let right = x.Right.Accept visitor

Add(left, right)

member v.Visit(x : Exp) =

Var x.Value }

But I'm still interested in knowing if there's another way ;))