On Tuesday, 28 May 2013 at 09:54:35 UTC, bearophile wrote:
The "rewrite rules" is a feature of the GHC compiler. It allows
the library writers to define rules that in most (or many)
cases are advantageous and lead to better optimization. As
example one of such rules swap map and filter, putting the
filter before the map, because this is more efficient. Haskell
allows you to perform such swapping because (nearly) everything
it does is pure and immutable.
Phobos does this a little bit in simple cases. For example,
retro(retro(r)) returns r if I remember correctly.
More complicated rewrites would be trickier to implement, and may
be impossible cross-modules (I cannot provide a rewrite for
retro(my.module.range) without modifying Phobos).
General rewrites, like the kind relational database query
optimisers do, require statistics on the data structures. For
example:
1) cartesianProduct(r1, r2).filter!(pred).sort("a[1]<b[1]")
2) cartesianProduct(r1, r2.sort("a[1]<b[1]")).filter!(pred)
Which is faster depends on the sizes of r1 and r2, and the pass
ratio of the filter predicate.
