Comment on Turn O(n^2) reverse into O(n)parentComments−xxpor12yIf you can derive this and prove it, shouldn't this optimization be done (theoretically) completely automatically by the compiler?−quchen12yComputers are good at verifying things, but bad at coming up with them.(An example for something computers can come up with is free theorems, but in this case that wouldn't have helped.)−Kutta12yThe rewriting part - if not the comping up with proofs part - is done automatically in quite a few libraries. You can specify the expression rewriting rules in pragmas in your source and GHC will carry them out.
Comments
If you can derive this and prove it, shouldn't this optimization be done (theoretically) completely automatically by the compiler?
Computers are good at verifying things, but bad at coming up with them.
(An example for something computers can come up with is free theorems, but in this case that wouldn't have helped.)
The rewriting part - if not the comping up with proofs part - is done automatically in quite a few libraries. You can specify the expression rewriting rules in pragmas in your source and GHC will carry them out.