泛型不那么通用!

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],斯卡拉将寻找一个隐含的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's和String's的例子:

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)
  }
}