Your existential solution is okay. It might be "prettier" to instead use a GADT
, as in:
{-# LANGUAGE GADTs #-}
data Shape where
Shape :: (Surface a) => a -> Shape
...and as leftaraoundabout suggests, you may be able to structure your code differently.
But I think you've basically hit up against the Expression Problem here; or perhaps, more accurately: by trying to structure your code cleverly (separate type for each shape with classes) in anticipation of the EP you've introduced new difficulties for yourself.
Check out the fun Data Types a la Carte by Wouter Swierstra for an elegant solution to what I hope is related to your problem. Maybe someone can comment with good packages on hackage to look at that are inspired by that paper.