리스트 비교하기 — 스칼라

스칼라에서 두 개의 리스트를 사전적 순서에 따라 비교하려고 한다. 어떻게 동작하는지 살펴보자.

scala> List(1,2) < List(1,2,3)
<console>:12: error: value < is not a member of List[Int]
       List(1,2) < List(1,2,3)
                 ^

List[Int] 타입에는 < 라는 멤버가 없다. Ordering 객체의 Implicits 멤버들을 가져와야 비교할 수 있다.

scala> import Ordering.Implicits._
import Ordering.Implicits._
scala> List(1,2) < List(1,2,3)
res9: Boolean = true

List[Int]에는 < 멤버가 없으니 Ordering.Implicits의 무언가를 통해 < 멤버를 가진 타입으로 바뀌어야 말이된다. Ordering.Implicits를 들여다 보자. 아래의 두 변환 함수만 정의되어 있다.

implicit def seqDerivedOrdering[CC[X] <: scala.collection.Seq[X], T](implicit ord: Ordering[T]): Ordering[CC[T]] =
      new Ordering[CC[T]] { ... }
implicit def infixOrderingOps[T](x: T)(implicit ord: Ordering[T]): Ordering[T]#Ops = new ord.Ops(x)

첫번째 seqDerivedOrdering 함수는 T가 Ordering을 가질때 Ordering[Seq[T]] 구현을 반환한다. Ordering[Int]는 이미 있으므로 Ordering[List[Int]] 변환이 자동으로 일어난다.

두번째 infixOrderingOps 함수는 Ordering[T]이 있을 때 T에 대해 <,> 같은 크기 비교 연산자를 구현한 래퍼객체로 변환해준다.

trait Ordering[T] {
  class Ops(lhs: T) {
    def <(rhs: T) = lt(lhs, rhs)
    def <=(rhs: T) = lteq(lhs, rhs)
    def >(rhs: T) = gt(lhs, rhs)
    ...
  }
}

모든 Implicit들을 Explicit하게 표현해 본다면 다음과 같다.

infixOrderingOps(List(1,2))(seqDerivedOrdering(Ordering.Int)).<(List(1,2,3)

(Implicit 없으면 어쩔뻔했어 ㅎ “Making Implicits Explicit — Scala” 도 참고)

그럼, 이제 구현을 찾았으니 스칼라의 리스트가 어떻게 “사전적 순서”로 비교를 하는지 살펴보자.

implicit def seqDerivedOrdering[CC[X] <: scala.collection.Seq[X], T](implicit ord: Ordering[T]): Ordering[CC[T]] =
  new Ordering[CC[T]] {
    def compare(x: CC[T], y: CC[T]): Int = {
      val xe = x.iterator
      val ye = y.iterator
      while (xe.hasNext && ye.hasNext) {
        val res = ord.compare(xe.next(), ye.next())
        if (res != 0) return res
      }
      Ordering.Boolean.compare(xe.hasNext, ye.hasNext)
    }
  }

특이한 부분은 Ordering.Boolean.compare를 이용하였다는 것! 이는 다시 java.lang.Boolean.compare로 이어진다.

형제글

• 리스트 비교하기 — 하스켈
• 리스트 비교하기 — 스칼라
• 리스트 비교하기 — 클로져