[Haskell-beginners] Create new value for given type

Hi, I'm given a type 'a' (lets assume the type is infinite) and a set finite 'xs'. Now I want to create a new value of type 'a' that does not occur in 'xs' and return a set 'ys' that consists of 'xs' and also contains the new value. How can I do this??? The types are known at compile time, so I would think it is possible in Haskell.. Greetings, Heinrich