Monotonic/Crease-handling

[pjonsson]

cc @emwap @emilaxelsson

The history of this ticket is that #38 exposed some expressions that should be optimized, for example min var3 (var3 >> 1). That optimization was checked in with the class Monotonic. Commit a23d9a1 renamed Monotonic to Crease, but that is not a great name. The optimization rule before that commit reads:

 constructFeatOpt _ (C' Min) (a :* b :* Nil)
        | as <- viewMonotonicDec a
        , any (alphaEq b) as = return a

I am convinced about the correctness of the optimization suggested in #38. Revisiting this generalization makes me a bit worried that the API is suggestive for making incorrect rewrite rules that will show upp in transitive uses, but I don't have a counter example at hand. I will try to construct a counter example this week.

The second issue is the name of the class. Aren't we really trying to Ord functions and their output?

f x < x

[pjonsson]

The last comment by @josefs identifies the property as inflationary, and the opposite is deflationary.

To call the class by a word that exists and means the right thing would be nice. Is it a trend we are trying to describe? We are not trying to calculate fix points, so Flationary that might be overkill for our situation. I'm still curious if ordering functions + their parameters compared to their output is enough for what we are after, in which case a partial Ord might suffice.

[emilaxelsson]

So you suggest a function

comp :: ASTF ... -> ASTF ... -> CompResult

?

That sounds nice, but one problem with using it in constructFeatOpt above is that we don't have direct access to the whole AST, only the symbol and its children.