rules

I'm curious when and how GHC applies rewrite rules, and how expensive it is. Felix also has rewrite rules. It uses a woefully expensive algorithm to apply them: 1) elide rules that refer to functions that have themselves been elided since they can't be applied. 2) For each rule in turn For each subexpression going down and up the subexpression tree, try to match the rule If there is a match perform a rewrite and set a 'modified' flag If the expression was modified, clear the flag and goto step 2. This process is 'more or less' applied before and after every other term rewriting (eg inlining) because reductions can create inlining opportunities, reduce the amount of inlining, but inlining also exposes new instances of rule patterns. AFAICS my algorithm is exponential or worse, however I assume it is still efficient simply because not many rule patterns turn up, and the ones that do get reduced away quickly. Felix allows these reductions in typeclasses, but it doesn't selectively apply them to functions using those classes -- the reductions are all performed globally (all rules on all code). -- John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net