Дженерики не так универсальны!

Question

Я попытался реализовать универсальный алгоритм двоичного поиска в Scala. Вот оно:

type Ord ={
def <(x:Any):Boolean
def >(x:Any):Boolean
}
def binSearch[T <: Ord ](x:T,start:Int,end:Int,t:Array[T]):Boolean = {
if (start > end) return false
val pos = (start + end ) / 2
if(t(pos)==x)         true
else if (t(pos) < x)  binSearch(x,pos+1,end,t)
else                binSearch(x,start,pos-1,t)
}

все в порядке, пока я не попытался его использовать (xD):

binSearch(3,0,4,Array(1,2,5,6))

компилятор делает вид, что Int не является членом Ord, но, как я знаю, класс Int имеет < и > методы. Что мне делать, чтобы решить эту странную проблему? Спасибо

Answer 1

Самое простое - использовать стандартную черту Scala Ordered[T] и сопровождающие ее неявные экземпляры.

Используя ограничение вида <% Ordered[T], Scala будет искать неявный экземпляр Ordered[T] в области действия и позволит вам использовать любой из его методов (например, <, >, >=, <= , compare) для универсального типа.

Вот слегка переписанная функция двоичного поиска,

def binarySearch[T <% Ordered[T]](x: T, xs: Seq[T]): Int = {

  def searchBetween(start: Int, end: Int): Int = {
    if (start > end) return -1 // not found

    val pos = (start + end ) / 2

    if (xs(pos) == x) pos // found, return position
    else if (xs(pos) < x) searchBetween(pos+1, end)
    else searchBetween(start, pos-1)
  }

  searchBetween(0, xs.length)
}

Затем вы можете сразу использовать его со многими распространенными классами, такими как Byte, Short, Int, Long, String, BigInt, ... в основном, с любым типом, для которого определяется Scala экземпляр Ordering[T] или даже предоставьте свой собственный, внедрив Ordering[YourType] и либо передав его явно binarySearch(), либо предоставив неявный экземпляр в области действия.

Вот примеры с Int и String:

scala> binarySearch(2, Seq(1,2,3,4,5))                               
res1: Int = 1

scala> binarySearch("d", Seq("a","b","d","f"))   
res2: Int = 2

Answer 2

Int действительно не относится к типу Ord. Он имеет <и>, но имеет тип Int, а не Any.

Я думаю, вам нужно использовать классы типов здесь:

trait Cmp[T] {
  def cmp(t1: T, t2: T) : Int
}

implicit object IntCmp extends Cmp[Int] {
  override def cmp(i1: Int, i2: Int) = i1 - i2
}

def binSearch[T](x:T,start:Int,end:Int,t:Array[T])(implicit c: Cmp[T]):Boolean = {
  if (start > end) return false
  val pos = (start + end ) / 2
  c.cmp(t(pos), x) match {
    case 0 =>  true
    case -1 =>  binSearch(x,pos+1,end,t)
    case _ => binSearch(x,start,pos-1,t)
  }
}

Answer 3

Удалите ваш Ord тип и измените ограничение типа T <: Ord на T <% Ordered[T]. Тогда все типы T, которые имеют неявные преобразования в Ordered[T] (включая числовые типы и String, например), будут приемлемыми.

Answer 4

Ну, почему Int должен быть подтипом Ord? Это, конечно, не объявлено.

Это не имеет ничего общего с обобщениями, но простой ООП: интерфейс реализуется, только если объявлен реализующий класс или один из его супертипов для реализации. Вы этого не делаете.

Редактировать: Оказывается, я был не прав. Я оставляю этот ответ из-за полезных комментариев к нему.