泛型不是很通用！

我试图在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是不是奥德的一员，但我知道类Int有<和>方法。那么我该怎么做才能解决这个奇怪的问题？谢谢

来源

2010-05-16 Aymen

我没有看到奥德是int类型看你的代码。 – 2010-05-16 12:00:24

最简单的就是使用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的和String的例子：

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

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

来源

2010-05-16 17:33:25

谢谢我试过'<：Ordered [T]'但我不知道'<％'的东西。 – Aymen 2010-05-16 18:56:17

您的二分查找不正确。尝试'binarySearch（2，Seq（1））'。它会超出界限 – user102008 2011-04-06 20:05:43

~~那么，为什么Int应该是Ord的子类？它当然没有被宣布为。~~

~~这与泛型没有任何关系，但是普通的OOP：只有在声明了实现类或其超类型之一时才实现该接口。你不这样做。~~

编辑：原来我错了。由于附有有用的评论，我留下了这个答案。

来源

2010-05-16 12:09:47 meriton

具有方法“<（Any）”和“>（Any）”的任何类都按照他定义的方式自动成为Ord的子类。不需要申报。问题在于，Int没有。 – sepp2k 2010-05-16 12:14:55

您应该阅读关于Scala中的结构类型。 http://goo.gl/3xbE – missingfaktor 2010-05-16 12:16:43

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

来源

2010-05-16 12:18:20 IttayD

好的谢谢你。这对我来说有点复杂（我刚刚开始学习scala），所以我现在只使用非泛型方法。 – Aymen 2010-05-16 12:24:56

放下你的Ord类型和T <: Ord改变类型约束T <% Ordered[T]。然后，所有类型T的隐式转换为Ordered[T]（包括数字类型和String，例如）将是可接受的。

来源

2010-05-16 14:33:52

泛型不是很通用！

回答

相关问题