This seems like it would be solvable by simply allowing interfaces to constrain generic parameters. Something like:

    func foo(type A Comparable, B OtherIface, C /* unconstrained */)(a A, b B) C {
        ...
    }

   func lookup(type A Indexable(B), B Hashable)(set A, idx B) {
       ...
   }