compilation of pattern-matching?

[Simon Peyton-Jones]

| >Indeed GHC does not attempt to retain the order of alternatives, although
| >a) it might be possible to do so by paying more attention in numerous places
| >b) GHC may do so already, by accident, in certain cases
|
| That adds even more unpredictability.
....
| very long list than the Cons-before-Nil order I wanted), but it is
| very frustrating if I'm not even given the chance because GHC
| sorts the alternatives, not even according to its own interpretation
| of branching performance, but completely arbitrarily!-)

All I'm saying is that GHC has never claimed to offer predictability here.  I understand that you find it frustrating, but there it is.  You are making a feature request.  Good!  Then someone needs to design it, and implement it in a way that is robust to the rather radical program optimizations that GHC does.  I don't think either is straightforward, and at the moment I am snowed under.

It is possible that such a change might allow you to tune programs better; although I doubt such tuning would be portable.  (Your 5% figures are encouraging, but it's one thing to get a 5% gain on one program, and quite another to get a positive figure on every program.   I spend a lot of time looking at nofib numbers where some programs respond well to some changed optimization, and others slow down.)   I'm also a bit concerned that it would impose a new constraint on the entire compilation chain.

Your idea of simply ordering patterns is certainly appealing from the programming point of view.  I don't yet see how to propagate that information through the pattern compilation algorithm, retain the resulting information in the optimizer, and exploit it in a code generator.  But it might well be possible. Maybe you can write a Haskell workshop paper about it?

Simon's idea of an annotation that gives some idea of the likelihood of the value of an expression taking a particular form sounds promising for robustness.  Something like
        Note "80% chance of (:), 20% of []" (f x)
But it's not so good when there are multiple interacting parameters to a pattern match.

Simon