It turns out you can use an equality type constraint instead of a conformance type constraint:
extension CollectionType where Generator.Element == AnyEquatable {
func indexOf(element : AnyEquatable) -> Index? {
return indexOf({ (currentElement : Generator.Element ) -> Bool in
element.equals(currentElement)
})
}
}
Discussion is ongoing at swift-evolution: [swift-evolution] Question about heterogeneous collections