Generics are not that common!
I tried to implement a generic binary search algorithm in scala. Here he 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 fine until i tried to use it (xD):
binSearch(3,0,4,Array(1,2,5,6))
the compiler pretends that Int is not a member of Ord, but as I know the Int class has methods <
and >
. So what should I do to solve this strange problem? thanks
a source to share
The simplest is to use a trait of the Scala standard library Ordered[T]
and its accompanying implicit instances.
Using the kind of constraint <% Ordered[T]
, Scala's will look for the implicit Ordered[T]
instance in the area of visibility and allow you to use any of its methods (such as <
, >
, >=
, <=
, compare
) on the common 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)
}
Then you can use it right away with a number of general classes, such as Byte
, Short
, Int
, Long
, String
, BigInt
, ... basically any type for which Scala defines an instance Ordering[T]
or even provides its own, implementing Ordering[YourType]
and either explicitly passing it in binarySearch()
, or by providing a copy of an implicit in the area of.
Here are examples with Int
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
a source to share
Int is really not of type Ord. It has <and>, but the types are 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)
}
}
a source to share
Well, why does Int have to be a subtype of Ord? This has certainly not been announced.
This has nothing to do with generics, but a simple OOP: an interface is only implemented if an implementing class or one of its supertypes is declared to implement it. You don't.
Edit: Turns out I was wrong. I am leaving this answer because of the helpful comments attached to it.
a source to share