I'm no fan of (!!) on lists or other containers where it isn't O(1), but lookup/member are a bit more promising. However are there any useful derived operations or constructions that can be defined only in terms of a Lookup type class? For comparison, Monoid has mconcat as a derived op and e.g. the Writer monad can be usefully abstract by relying only on the Monoid interface as can Foldable.
I was thinking of (!!) as an unsafe lookup, where lookup is the safe one. Of course historically (!!) considers lists as (Int -> elt) while elem considers them a set, which is why you'd need some newtype wrappers. Anyway, I'd be happy to not include the unsafe variants at all. That would mean putting [] into Setlike with 'member' but not Maplike with 'lookup'. You'd have to come up with a better name or hide the Prelude alist lookup. I don't know about derived operations, I suppose you could come up with some sort of Evironment monad that required merely a (Maplike a) class constraint instead of a concrete data type like Map, but for me the prime motivation would be the short universal name. I could stick it in my "import unqualified" toolbox and type less.
Excepting Data.Tree, Data.Graph and HashTable, 'containers' seems pretty regular now - it certainly has moved on with 0.3.0.0.
Yes, and it's not a big deal to me. I use Map and Set and List and the overhead of separate functions for each is pretty minimal. If I used a wider variety of containers I'd probably want it more.