제네릭이 너무 일반적이지 않습니다!

Question

나는 스칼라에서 일반 이진 탐색 알고리즘을 구현하려고 시도했다. (의 xD)

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

모든 것을 내가 실제로 그것을 사용하려고 할 때까지 OK입니다 : 여기있다

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

컴파일러는 지능이 오드의 멤버가 아닌 척하지만, 나는 클래스를 알고 Int는 < 및 > 방법이 있습니다. 그럼이 이상한 문제를 해결하려면 어떻게해야합니까? 감사합니다.

Answer 1

가장 쉬운 것은 스칼라의 표준 라이브러리 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로 사용할 수 있습니다

, ... 기본적으로 모든 종류의 스칼라가 Ordering[T] 인스턴스를 정의하거나 심지어 Ordering[YourType]을 구현하고 binarySearch()에 명시 적으로 전달하거나 범위에 암시 적 인스턴스를 제공하여 직접 제공 할 수도 있습니다.

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의 하위 유형이되어야합니까? 그것은 분명히 선언되지 않았습니다.

이것은 제네릭과는 아무런 관련이 없지만 일반 OOP : 인터페이스는 구현 클래스 또는 해당 수퍼 유형 중 하나가이를 구현하도록 선언 된 경우에만 구현됩니다. 너는 그렇게하지 않는다.

편집 : 내가 잘못했음을 알립니다. 첨부 된 도움이되는 의견으로 인해이 답변을 남깁니다.

Answer 3

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 4

이 Ord 유형을 삭제하고 T <% Ordered[T]에 유형의 제약 조건을 T <: Ord을 변경합니다. 그러면 Ordered[T] (예 : 숫자 유형 및 String 포함)으로 암시 적으로 변환되는 모든 유형 T이 허용됩니다.