Generics not so generic !!

Question

Hi I tried to implement a generic binary search algorithm in scala. Here it is :

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

everything is OK until I tried to actually use it (xD) :

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

the compiler is pretending that Int is not a member of Ord, but as I know class Int has <and > methods. Well what shall I do to solve this weird problem? Thanks

Answer 1

Int is indeed not of type Ord. It has < and > , but the types are of Int, not Any.

I think you need to use type classes here:

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 2

Drop your Ord type and change the type constraint T <: Ord to T <% Ordered[T]. Then all the types T that have implicit conversions to Ordered[T] (including the numeric types and String, e.g.) will be acceptable.

Answer 3

Easiest is to use Scala's standard library Ordered[T] trait and its accompanying implicit instances.

By using a view bound <% Ordered[T], Scala will look for an implicit Ordered[T] instance in scope and allow you to use any of its methods (e.g. <, >, >=, <=, compare) on the generic type.

Here's a slightly rewritten binary search function,

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

You can then immediately use it with many common classes, such as Byte, Short, Int, Long, String, BigInt, ... basically any type for which Scala defines an Ordering[T] instance, or even provide your own by implementing an Ordering[YourType] and either passing it explicitly to binarySearch() or providing an implicit instance in the scope.

Here are examples with Int's and 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