[Many excellent ideas on Active Patterns removed]

Jon Harrop wrote:
> That could be written much more elegantly, something like this:
>
> let rec rewrite rule = function
>   | Int _ | Var _ as f -> rule f
>   | Add(f, g) -> Add(rewrite rule f, rewrite rule g)
>   | Mul(f, g) -> Mul(rewrite rule f, rewrite rule g)
>   
Following ideas of Barry Jay, this could be even more simply written as
let rec rewrite rule = function
  | u _ as f -> rule f
  | b(f, g) -> b(rewrite rule f, rewrite rule g)

where u and b are supposed to be bound (to respectively unary and binary 
constructors).

Yes, the 'type' of the function rewrite needs higher-order polymorphism 
(or polytypism or ...) to work.  See Tim Sheard's Omega for one rather 
nice way to do that.

Jacques