[Haskell-cafe] Re: Properties of optimizer rule application?

Roman Leshchinskiy rl at cse.unsw.edu.au
Wed Jan 16 19:10:44 EST 2008

Henning Thielemann wrote:
> To give a precise example: If I have a sequence of 'map's
>   map f0 . map f1 . ... . map fn
>  then there is some length where this is no longer collapsed to a single
> 'map'? 

No. After applying a rule, the simplifier optimises the result of the 
rewriting. This means that with (map f (map g x) = map (f . g) x),

   map f (map g (map h xs))

is first rewritten to

   map (f . g) (map h xs)

and the immediately to

   map (f . g . h) xs

Rewriting does not shift the "focus" of the simplifier.

>    project . project . foo
>  with the rules
>    project (project x) = project x
>    project (foo     x) = projectFoo x
> Both rules can be applied to the expression, but you get one fusion more,
> if you use the first one first. Let me guess, in order to solve that, I
> should restrict the first rule to an earlier phase than the second rule.

That's one possibility. It would be vastly preferable, however, to add 
the rule

   project (projectFoo x) = projectFoo x

In general, you want your rewrite system to be confluent. I suspect that 
  non-confluence always indicates a design problem. This is within one 
set of rules, of course - explicitly staged things like "rewriting back" 
of stuff which didn't fuse are different.


More information about the Haskell-Cafe mailing list