Optimal representation of expressions in F#

Question

I'm working on a library to generate SQL from LINQ expressions (basically a modified subset of LINQ-to-SQL). I'm using discriminated unions to model the SQL expressions, but have encountered some (perceived?) limitations. I want to do something like the following (note the last line):

type SqlSourceExpression =
    | Table of string
    | Join of JoinType * SqlSourceExpression * SqlSourceExpression * SqlExpression //ie, left, right, predicate

and SqlExpression =
    | Source of SqlSourceExpression
    | OrderBy of SqlExpression * SortDirection
    | Select of SqlSourceExpression * SqlExpression * OrderBy list //can't do this

I could do the following:

type SqlOrderByExpression = SqlExpression * SortDirection

...and change the last two lines to:

    | OrderBy of SqlOrderByExpression
    | Select of SqlSourceExpression * SqlExpression * SqlOrderByExpression list

But that appears to have two problems:

1. SqlOrderByExpression is not a SqlExpression. This makes it hard to use the visitor pattern (maybe herein lies the problem?). Which means when traversing a Select expression I can't iterate over the list of order by expressions passing each one to Visit(expr:SqlExpression).

2. SqlOrderByExpression is merely a type alias for a tuple, so no type information is preserved. That hurts readability IMO.

Is there a better way to model this? I tried the inheritance route, but I think DUs are MUCH easier to work with (barring the noted difficulty).

Answer 1

I'm not sure why SqlExpression, as a discriminated union, has cases for OrderBy and Select. What's allowed to go inside an OrderBy?

I think discriminated unions are making this more difficult than it needs to be. I think SqlSourceExpression, SqlOrderByExpression and SqlSelectExpression can be different types. You can make them records if you're worried about tuples being difficult to read (this is what I'd do in your situation).

I think an SqlExpression discriminated union will come in useful when you start to represent expression trees like (1 + SUM(ISNULL(Value1, Value2))) / COUNT(*), where the syntax is more flexible.

Answer 2

As you work with FP technique (DU), as you don't need to remember OOP patterns, just use high-order functions (fold, map, zippers, etc).

In case you just want to specific view for your matching code, there is active patterns:

let (|OrderByTerm|OrderByList|_|)= function
  |OrderBy x -> Some (OrderByTerm x)
  |Select (_,_,xs) -> Some (OrderByList xs)
  |_ -> None