리스트 비교하기 — 하스켈

리스트를 비교하는 기본방법은 ‘사전적 순서(lexicographical order)’에 따라 비교하는 것이다. 하스켈의 리스트를 비교하는 것도 사전적 순서에 따른다. 음, 정말일까?

Prelude> "가" < "가나다"
True
Prelude> "나" < "가나다"
False

몇가지 테스트해보면 맞는 것 같다. 그런데, 정말 그런지 소스 코드로 직접 확인해보고 싶다.

먼저, 위의 (<) 연산자는 문자열을 비교하는데 그치지 않는다. Ord 클래스에 정의된 함수이기 때문이다. Ord 클래스에는 크기 비교와 관련된 여러가지 함수/연산자가 정의되어 있다. 최소 정의는 compare 나 (<=).

class Eq a => Ord a where
    compare :: a -> a -> Ordering
    (<) :: a -> a -> Bool
    (<=) :: a -> a -> Bool
    ...

리스트도 Ord 인스턴스를 가진다는 얘기다. 그런데… 리스트의 경우는 Ord 인스턴스를 찾을 수 없다.

리스트의 Ord 인스턴스에서 소스 코드 링크를 찾을 수 없다.

사실 대부분의 경우 Ord 인스턴스를 찾을 수 없다. 왜냐하면 자동 생성에 의존하는 경우가 대부분이니까! Ord 인스턴스의 자동 생성 규칙은 Haskell 98 리포트 10.1에 짧게 설명되어 있다.

Haskell 98 리포트 10.1

Datatype의 생성자 순서 및 인자 순서에 따라 “사전적 순서”로 구현된다고 한다. 리스트는 Haskell 98 리포트 8장의 Prelude에 아래와 같이 정의되어 있다.

data  [a]  =  [] | a : [a]  deriving (Eq, Ord)
   -- Not legal Haskell; for illustration only

Ord 인스턴스 생성 규칙과 리스트 타입의 정의로부터 리스트 크기 비교가 어떻게 동작하는지 결정된다. 예를 들어 빈 리스트는 비어 있지 않은 리스트보다 작다는 것도 확인할 수 있다.

소스코드로 확인하고자 했지만 스펙만 확인한 셈이 됐다.

규칙대로 Eq와 Ord 인스턴스를 만든다면 아마도 아래와 같을 것이다.

data [a] = [] | a : [a]
instance (Eq a) => Eq [a] where
  []     == []        = True
  (a:as) == (b:bs)    = a == b && as == bs
  _      == _         = False
instance (Ord a) => Ord [a] where
  []     <= _         = True
  _      <= []        = False
  (a:as) <= (b:bs)    = (a < b) || (a == b && as <= bs)

형제글

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