What (if any) criteria are there for choosing types for input parameters and return values for methods?

One principle (pattern even) could be named WideParameterNarrowReturn:

For any parameter, choose the least specific type that your usage of it allows.

For the return type use the most specific type that your implementation supports

Example in java:
     Collection removeDuplicates(Vector v){...}
should be rewritten to
     T''''''reeSet removeDuplicates(Collection c){...}

----
'''Pros:'''
It will be easier for you to reuse the method some other time because you will be able to removeDuplicates from, say, an A''''''rrayList without rewriting the method. Similarly if you happen to need a T''''''reeSet in the place where you use the method you will not have to construct a new one.

----
'''Cons:'''
If your implementation changes you might have to write strange code in order not to break code that already uses your method.

In fact this might even be enough to adopt the opposite principle NarrowParameterWideReturn or at least UseWideReturnTypes

----
So there seems to be a conflict here. Did anybody think this through?

''Yes, many people have thought it through but since we are not dealing with truths there are differing opinions (surprisingly, as LucaCardelli says, see http://sern.ucalgary.ca/courses/SENG/609.03/W98/Abadi/AbadiCh2.html#2.6). The case for narrow return is easily understood but the wide (=contravariant) parameter is not so clear.'' --AndrewQueisser

This paper deals with the technicalities of co/contravariance and I agree with the author when he states that ''It is amazing that there is any argument'' ;-) However, the question is not so much what the language allows but more about what is actually good practice even when no inheritance is involved. --JanLarsen

''I guess we should stick to: "The opposite of every truth is also true."''  (Not everything that implies a true statement is true, and, amusingly, neither is this.)
----
see CovariantReturnTypes