which should be a no-op at runtime because the representation of Foo x and x are the same, but due to the newtype, the traversal does need to occur. [1] discusses a way to avoid these problems. Basically these newtype should only ever be needed during type checking, and should really be erased after that; once you've type checked everything, then you know your program won't ever treat something which is a non Foo Int as an Int, so you can then get rid of the compile time tag and gain better optimisations.
[1] http://research.microsoft.com/en-us/um/people/simonpj/papers...