Check numeric constraint expressions for equivalence/subset of allowed values

Question

I have an AST representing expressions like these:

• (<=10 && >=3) || ==0
• ==1 || ==2 || ==3
• ==1 && !=1

There are numerics as well as boolean (||, &&) and numeric (<, <=, ==, !=, >=, >) operators. A boolean not operator can be added to the AST if needed. These expressions are used to constrain possible numeric input values (note that the last one does not allow anything).

I am looking for a way of comparing two expressions. I need to know if they allow the exact same set of numbers (are equivalent), or if one expression permits a subset of the other one.

Answer 1

You can write a function

evaluate :: Expression -> ValueSet

that evaluates an expression into a set of values where it is true. This value set could be something like

data Value = MinusInfinity | Finite Integer | PositiveInfinity
type Range = (Value, Value)
type ValueSet = [Range]

where ValueSet is a sorted list of closed, disjoint ranges. Then you can implement the cases of evaluate one by one using logic that resembles a sorted merge.