efficiency

[Feuer]

In  http://www.cs.columbia.edu/~cdo/icfp99.ps Okasaki does a couple
things I'm not sure I quite understand:

He has a datatype
newtype Empty a = E ()

I cannot for the life of me figure out why he didn't just do
data Empty a = E

The other weird thing was:

newtype Pair v w a = P (v a, w a)

I can't see why he didn't do

data Pair v w a = P (v a) (w a)

I was wondering if anyone on this list knew of any reasons the types he
chose would be more efficient than mine....

David