Structural subtyping, Upper bounds, Implicite Parameter & View bounds

Scala에서 insertion sort는 다음과 같이 구현할 수 있습니다.

def isort[T](less:(T,T)=>Boolean)(xs:List[T]):List[T] = {
  def insert(x:T, xs:List[T]):List[T] = xs match {
    case Nil => List(x)
    case x1::xs1 => if (less(x, x1)) x::xs else x1::insert(x, xs1)
  }
  xs match {
    case Nil => Nil
    case x::xs1 => insert(x, isort(less)(xs1))
  }
}
  
println(isort((x:Int, y:Int)=> x < y)(List(2, 6, 3, 1, 5, 4))  
// List(1, 2, 3, 4, 5, 6)
println(isort((x:Char, y:Char) => x < y)(List('스', '칼', '라', '언', '어')  
// List('라', '스', '어', '언', '칼')

Int형이라면 < 연산자를 사용하고 비교하기 위해 less 연산자를 사용하지 않겠지만 Double이나 Char를 정렬하고 싶은 경우도 생기기 때문에 일반적인 형 T에 대해 사용할 수 있도록 적은 것입니다. 하지만 Double, Char 모두 < 연산자를 제공하고 있는데 반복적인 less를 사용하는 것이 불편합니다.
Programming Scala 책에는 structural subtype에 대해 클래스 이름이 아니라 특정한 메소드를 가지는 것으로 subtype을 결정하는 것이라고 나와 있습니다. 다음과 같이 시도해 봅니다.

def isort2[T <: { def <(other:T):Boolean }](xs:List[T]):List[T] = {
  def insert(x:T, xs:List[T]):List[T] = xs match {
    case Nil => List(x)
    case x1::xs1 => if (x < x1) x::xs else x1::insert(x, xs1)
  }
  xs match {
    case Nil => Nil
    case x::xs1 => insert(x, isort(xs1))
  }
}

위에서 의미하고자 하는 것은 같은 형과 비교하는 연산자 <를 가지는 클래스 T를 말하는 것입니다만, structural subtype에서는 아직 정의되지 않은 T를 사용할 수 없다며 컴파일 오류가 발생합니다. 다른 형의 메소드라면 이 방법으로 해결할 수 있었겠지만 같은 형을 비교해서 Boolean을 반환하는 함수형은 이 방법을 사용할 수 없습니다.
Scala에는 두가지 값을 비교하는 경우에 대해 Ordered trait이 정의되어 있습니다. Trait에 abstract로 정의된 compare 함수를 정의하면 <, <=, > >= 등의 연산자가 자동으로 지원되는 것입니다.

def isort3[T <: Ordered[T]](xs:List[T]):List[T] 

위와 같이 정의를 바꾸면 Ordered trait을 확장한 클래스만 사용할 수 있고 Int, Double, Char 등은 Ordered trait을 확장하지 않았으므로 호출 부분에서 형 오류가 발생합니다. 이때 사용할 수 있는 것이 implicit conversion 입니다. 형이 맞지 않을 때 컴파일러가 자동으로 형 변환을 해 주는 것입니다. 이를 위해서는 인자 선언시 implicit 키워드를 사용해 주면 됩니다.

def isort4[T](xs:List[T])(implicit orderer:T => Ordered[T]):List[T] = {
  def insert(x:T, xs:List[T]):List[T] = xs match {
    case Nil => List(x)
    case x1::xs1 => if (orderer(x) < x1) x::xs else x1::insert(x, xs1)
  }
  xs match {
    case Nil => Nil
    case x::xs1 => insert(x, isort4(xs1)(orderer))
  }
}

원래는 Int, Double, Char 형에서 Ordered 형으로 변환하는 함수도 implicit 키워드로 정의해야 하지만 많이 사용되는 관계로 scala.Predef에 정의되어 있다고 합니다. Int, Double, Char 형에서 기본적으로 Ordered trait을 확장하지 않은 것은 java의 자료형을 그대로 사용하고 속도 문제이기 때문이라고 생각합니다. 따라서 위와 같이 정의하면 isort4(List(2, 6, 3, 1, 5, 4))와 같이 변환 함수를 지정하지 않고 호출해도 컴파일러가 자동으로 변환 함수를 붙여서 호출해 줍니다. 심지어 함수 내부에 사용된 orderer 또한 생략할 수 있습니다.
이와 같은 implicit parameter가 많이 사용되므로 scala에서는 type의 bound와 비슷하게 view bound로 지원합니다. 따라서 함수를 다음과 같이 정의하고 사용할 수 있습니다.

def isort5[T <% Ordered[T]](xs:List[T]):List[T] = {
  def insert(x:T, xs:List[T]):List[T] = xs match {
    case Nil => List(x)
    case x1::xs1 => if (x < x1) x::xs else x1::insert(x, xs1)
  }
  xs match {
    case Nil => Nil
    case x::xs1 => insert(x, isort(xs1))
  }
}

T <% Ordered[T]가 의미하는 것은 클래스 T가 암시적(implicit)으로 Ordered[T]로 변환 가능해야 한다는 조건을 거는 것입니다. Int, Double, Char 모두 위의 조건을 만족하므로 비교하기 위한 메소드를 따로 지정하지 않고 호출할 수 있으며 컴파일러는 형을 변환하는 작업을 자동으로 해 줍니다.

가려운 곳을 시원하게 긁은 기분입니다만, 컴파일러는 굉장히 복잡한 작업을 해야 하는군요.