리스트 비교하기 — 클로져

클로져에서 두 리스트를 사전적 순서에 따라 비교하려고 한다. 어떻게 하나 살펴보자.

(println (< [1 3] [1 2 3]))
;; PersistentVector cannot be cast to java.lang.Number

아쉽게도 < 연산자는 Number에 국한된다. 대신 compare로 비교할 수 있다.

(compare [1 3] [1 2 3])
;; -1

앗, 그런데 사전적 순서에 어긋난다. 왜 그럴까?

If you do not specify your own comparator, sorting is done by a built-in function compare. compare works for many types of values, ordering them in one particular way: increasing numeric order for numbers; lexicographic order (aka dictionary order) for strings, symbols, and keywords; shortest-to-longest order by Clojure vectors, with lexicographic ordering among equal length vectors. All Java types implement the Comparable interface such as characters, booleans, File, URI, and UUID are compared via their compareTo methods. Finally, nil can be compared to all values described earlier, and is considered less than everything else. See compare for examples and more details.

— http://clojure.org/guides/comparators

이런! 클로져 벡터는 짧은 것보다 긴 것을 “크다”고 보며, 길이가 같은 경우에만 사전적 순서로 비교한단다.

실제 코드를 살펴보자. 함수 (compare x y)는 내부적으로 x.compareTo(y)와 동일하다. 그러면 벡터 타입에 정의된 compareTo를 살펴보면 된다. 다음은 clojure/src/jvm/clojure/lang/APersistentVector.java 에 정의된 compareTo 메쏘드이다.

public int compareTo(Object o){
  IPersistentVector v = (IPersistentVector) o;
  if(count() < v.count())
    return -1;
  else if(count() > v.count())
    return 1;
  for(int i = 0; i < count(); i++)  {
    int c = Util.compare(nth(i),v.nth(i));
    if(c != 0)
      return c;
  }
  return 0;
}

앞의 설명처럼 길이를 비교하고, 길이가 같은 경우에만 사전적 순서로 비교한다. 아무래도 클로져에서는 벡터의 사전적 순서 비교는 직접 구현해야 할 것 같다. 아래처럼 구현해볼 수 있을 것이다.

(defn lexicomp [a b]
    (let [la (count a)
          lb (count b)]
        (loop [i 0]
            (if (and (< i la) (< i lb))
                (let [comp (compare (nth a i) (nth b i))]
                     (if (= 0 comp)
                         (recur (inc i))
                         comp))
                (compare la lb)))))
(println (lexicomp [1 3] [1 2 3]))   ; 1
(println (lexicomp [1 1] [1 2 3]))   ; -1
(println (lexicomp [1 2] [1 2 3]))   ; -1
(println (lexicomp [1 2 3] [1 2 3])) ; 0

형제글

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