Building flat quoted lambda

Question

I'm using quotations in F# to build a function which checks whether a single input satisfies any of a number of cases. That is, a function whos body is something like ... || ... || ..., where the number of ||s is determined at runtime. Somewhat simplified, what I have now is

let vals = [|1..3|]
let currentfilter =
    vals
    |> Array.fold (fun acc i ->
        <@ fun j -> (%acc) j || j = i @>)
        <@ fun _ -> false @>

which generates the tree

val currentfilter : Expr<(int -> bool)> =
  Lambda (j,
        IfThenElse (Application (Lambda (j,
                                         IfThenElse (Application (Lambda (j,
                                                                          IfThenElse (Application (Lambda (_arg1,
                                                                                                           Value (false)),
                                                                                                   j),
                                                                                      Value (true),
                                                                                      Call (None,
                                                                                            op_Equality,
                                                                                            [j,
                                                                                             Value (1)]))),
                                                                  j),
                                                     Value (true),
                                                     Call (None, op_Equality,
                                                           [j, Value (2)]))), j),
                    Value (true), Call (None, op_Equality, [j, Value (3)])))

Optimally, what I want to generate is more like

  Lambda (j,
        IfThenElse (IfThenElse (Call (None, op_Equality, [j, Value (1)]),
                                Value (true),
                                Call (None, op_Equality, [j, Value (2)])),
                    Value (true), Call (None, op_Equality, [j, Value (3)])))

(This was generated by <@ fun j -> j = 1 || j = 2 || j = 3 @>)

Is there any easy way of flattening the first expression, in order to make it look more like the second?

Answer 1

You can write the code so that it does not return quoted function but instead returns a function that generates quotation when given the input:

let vals = [|1..3|]

let currentfilter =
    vals |> Array.fold (fun acc i ->
        fun j -> <@ %(acc j) || %j = i @>)
        (fun _ -> <@ false @>)

In the fold:

• Initial value is a function that returns false expression
• Aggregation composes the expression generated so far with an expression that compares the input (specified as a quotation) with the value i.

Now, to create the complete quoted function, we would like to write something like this:

<@ fun j -> %(currentfilter <@ j @>) @>

Sadly, this does not work - because the F# compiler is a bit strict here and does not let us write code where the variable j could escape its scope (quite reasonable, but unfortunate).

So, instead, you can write this by constructing the quotation manually:

open Microsoft.FSharp.Quotations

let v = Var.Global("j", typeof<int>)
Expr.Lambda(v, currentfilter (Expr.Cast(Expr.Var(v))))