Cyclic type reference in f#

Question

I am writing simple excel formula to linq expressions builder in F#. I'm parsing formulas to AST and building expressions using recursive expression builder. I've stucked on passing environment (map of (string, expression) pairs) to generated expression in that call:

Expression.Lambda<System.Func<double>>(eval pexpr).Compile()

Where pexpr is parsed AST and eval is expression builder function.

The problem is with defining type that should look like this:

type ExprFunc = Func<ExprFunc map, double>
Expression.Lambda<ExprFunc>(eval pexpr).Compile()

If pexpr contains reference to other expression in form of Var("name"), i want to inject expression that searches function with "name" in environment map and call it, passing the same environment map in that call.

Unfortunately, compiler says no:

This type definition involves an immediate cyclic reference through an abbreviation

Is there any way to define such function type in .net?

Answer 1

If you want to write a type declaration that references itself, you cannot use F# type alias. The problem is that an F# type alias is erased at compile-time, so a recursive reference would lead to an infinite type:

Func<Func<Func<Func<... map, double> map, double> map, double> map, double>

In F#, the easiest alternative is probably to define a simple discriminated union:

type ExprFunc = EF of Func<ExprFunc map, double> 

Then you can use the pattern EF f to get the underlying delegate in an F# function. Doing this directly won't work with Expression.Lambda though, so you'll probably need something like:

type ExprFunc = Func<ExprFunc map, double> 
and WrappedExprFunc = EF of ExprFunc

When calling Expression.Lambda, you'll need to use the Func<..> delegate as an argument, but you'll need to modify the code in eval to properly handle wrapped arguments (which will be of type WrappedExprFunc):

Expression.Lambda<ExprFunc>(eval pexpr).Compile()   

As an aside, if you're generating C# expression trees, it might be easier to define WrappedExprFunc as a class, because that is easier to process. That depends on the rest of your code.