Lambdabot (on #haskell) has something similar using a type, Expr, to overload certain names, e.g.
koninkje > foldr f z [1..5] lambdabot f 1 (f 2 (f 3 (f 4 (f 5 z))))
It's a complete hack and isn't as sophisticated as what you're after, but it could serve as a basis for implementation ideas.
I'm aware of the Expr stuff in lambdabot and elsewhere. This is not quite what I need, perhaps I should have picked an example that doesn't almost-work with Expr. I need something that will symbolically evaluate a complex non-numeric expression that makes use of GADTs. I'm thinking it might not be too hard to implement using TH, but haven't tried yet... (though not sure if TH supports GADTs).
Live well, ~wren
Tim Newsham http://www.thenewsh.com/~newsham/