How do you decide what goes in an interface?

I've been having an interesting talk with Doug McClean about appropriate locations of methods. We're discussing if the ICollection<A> interface should include the Transform method. Specifically should the interface look like this:

 public interface ICollection<A> {
     ...
     ICollection<B> Transform<B>(IBijection<A,B> bijection);
     ...
}

Doug thinks (feel free to correct me Doug and I'll update this page) that Transform isn't really appropriate on the main collection interface because it carries a burden on consumers of the ICollection interface to understand it. Instead it should be pushed down a specialized subinterface (like ITransformableCollection) and a dummy implementation on a helper class. i.e.

 public static class CollectionHelpers {
    public static ICollection<B> Transform<A,B>(ICollection<A> collection, IBijection<A,B> bijection) {
        ITransformableCollection<A> tc = collection as ITransformableCollection<A>;
        if (tc != null) {
            tc.Transform<B>(bijection);
        }

        return new TransformedCollection<A,B>(collection, bijection);
    }
}

(where TransformedCollection is a specialized class that uses the bijection to pass values to and from the underlying collection).

I was thinking about this and trying to determine how you decide what should go on an interface. One could make the argument that you should keep the interface as simple as possible and only provide the bare minimum of methods that give you full funcationality. However, if I were to take that argument to it's logical conclusion than the entire ICollection interface would look like:

 public interface ICollection<A> {
     B Fold(Function<B,Function<A,B>>, B accumulator);
}

Using that one could get every other bit of functionality that is in the list interface. You could implement 'ForAll', 'Exists', 'Find','Count', 'Iterate', 'Transform', 'FindAll', 'Filter', and everything else in the current interface on top of Fold. However, this wouldn't be a very convenient interface to use. All you'd ever see was folds and you'd always be asking yourself "what is this fold doing?" Chances are a lot of those times you'd be doing something like 'counting' or 'finding an element'. And so one could argue "certain actions that people commonly do on a collection should be pushed into the interface". So what happens when you run into a method like 'Transform'. I've already run into cases where I've needed it. However, is it common enough that other people will run into it? Or is it something that will be used all of 0.01% of the time. Is that enough to keep it in the interface? Should that even be part of the criteria?

I'd love thoughts on this problem, addressing this issue if possible, or other cases where you're run into this.