파생 인스턴스의 명세

파생 인스턴스의 명세 (Specification of Derived Instances)

deriving 키워드를 쓰면 data 타입에 대해 Eq, Show 같은 클래스의 인스턴스가 자동으로 만들어진다는 건 앞에서 봤죠. 그런데 정확히 "어떻게" 만들어지는 걸까요? 이 장은 파생 인스턴스가 각 클래스에 대해 정확히 어떤 규칙으로 생성되는지, 그리고 언제 파생이 가능한지를 명세해요. 자동으로 만들어지는 코드의 동작을 정확히 알고 싶다면 이 장이 답이에요.

출처: Haskell 2010 언어 리포트

본문

파생 인스턴스(derived instance)는 data나 newtype 선언과 함께 자동으로 생성되는 인스턴스 선언이에요. 파생 인스턴스 선언의 본문은 연관된 타입의 정의에서 구문적으로 파생돼요. 파생 인스턴스는 컴파일러가 아는 클래스 — Prelude나 표준 라이브러리에 정의된 것 — 에 대해서만 가능해요. 이 장은 Prelude가 정의한 클래스들의 파생을 설명해요.

T가 다음과 같이 선언된 대수적 데이터타입이라면:

data cx => T u1 … uk = K1 t11 … t1k1 |  | Kn tn1 … tnkn
                        deriving (C1, …, Cm)

(여기서 m ≥ 0이고 m = 1이면 괄호는 생략 가능) 클래스 C에 대한 파생 인스턴스 선언은 다음 조건들이 성립할 때 가능해요:

  • C는 Eq, Ord, Enum, Bounded, Show, Read 중 하나.
  • 각 성분 타입 tij에 대해 cx′ ⇒ C tij를 성립시키는 문맥 cx′가 존재.
  • C가 Bounded면, 타입은 열거형이거나(모든 생성자가 무인자) 생성자가 하나뿐이어야 함.
  • C가 Enum이면, 타입은 열거형이어야 함.
  • 프로그램 다른 곳에 T u1 … uk를 C의 인스턴스로 만드는 명시적 인스턴스 선언이 없어야 함.
  • data 선언에 생성자가 없으면(n = 0) 파생 가능한 클래스도 없음(m = 0).

파생 인스턴스 목적상 newtype 선언은 생성자가 하나인 data 선언으로 취급돼요.

deriving 형태가 있으면 각 클래스 Ci에 대해 T u1 … uk 위의 인스턴스 선언이 자동 생성돼요. 어떤 Ci에 대해 파생 인스턴스 선언이 불가능하면 정적 오류가 나요. 파생 인스턴스가 하나도 필요 없으면 deriving 형태를 생략하거나 deriving () 형태를 쓸 수 있어요.

각 파생 인스턴스 선언은 다음과 같은 형태를 가져요:

instance (cx, cx′) => Ci (T u1 … uk) where { d }

여기서 d는 Ci와 T의 데이터타입 선언에 따라 자동으로 파생돼요. 문맥 cx′는 위의 (2)를 만족하는 가장 작은 문맥이에요. 상호 재귀 데이터타입에 대해 컴파일러는 그것을 계산하기 위해 고정점 계산을 수행해야 할 수 있어요.

이제 파생 가능한 각 Prelude 클래스의 나머지 세부 사항을 봐요. 이 번역에 쓰이는 자유 변수와 생성자는 항상 Prelude가 정의한 개체를 가리켜요.

11.1 Eq와 Ord의 파생 인스턴스

Eq와 Ord의 파생 인스턴스가 자동으로 도입하는 클래스 메서드는 (==), (/=), compare, (<), (<=), (>), (>=), max, min이에요. 뒤의 일곱 연산자는 주어진 생성자 집합에 대해 인자들을 사전식(lexicographic)으로 비교하도록 정의돼요 — 데이터타입 선언에서 더 앞에 있는 생성자가 더 작은 것으로 쳐요. 예를 들어 Bool 데이터타입에서 (True > False) == True예요.

파생 비교는 항상 생성자를 왼쪽에서 오른쪽으로 훑어요. 다음 예가 이 성질을 보여줘요:

(1,undefined) == (2,undefined)  ⇒  False
(undefined,1) == (undefined,2)  ⇒  ⊥

Eq와 Ord 클래스의 모든 파생 연산은 두 인자 모두에 엄격해요. 예를 들어 False <= ⊥는 ⊥이에요. False가 Bool 타입의 첫 생성자임에도 말이죠.

11.2 Enum의 파생 인스턴스

클래스 Enum의 파생 인스턴스 선언은 열거형(무인자 생성자만 있는 데이터타입)에 대해서만 가능해요.

무인자 생성자는 왼쪽에서 오른쪽으로 인덱스 0부터 n−1까지 번호가 매겨진다고 가정해요. succ와 pred 연산자는 이 번호 체계에서 각각 값의 다음/이전을 줘요. 최대 원소에 succ를, 최소 원소에 pred를 적용하는 것은 오류예요.

toEnum과 fromEnum은 열거 값을 Int 타입으로/에서 매핑해요. toEnum은 Int 인자가 생성자 중 하나의 인덱스가 아니면 실행 오류를 일으켜요. 나머지 메서드의 정의는:

enumFrom x = enumFromTo x lastCon
enumFromThen x y = enumFromThenTo x y bound
  where
    bound   | fromEnum y >= fromEnum x = lastCon
            | otherwise                = firstCon
enumFromTo x y = map toEnum [fromEnum x .. fromEnum y]
enumFromThenTo x y z = map toEnum [fromEnum x, fromEnum y .. fromEnum z]

여기서 firstCon과 lastCon은 각각 data 선언에 나열된 첫/마지막 생성자예요. 예를 들어:

data Color = Red | Orange | Yellow | Green deriving (Enum)

면 다음이 성립해요:

[Orange ..] == [Orange, Yellow, Green]
fromEnum Yellow == 2

11.3 Bounded의 파생 인스턴스

Bounded 클래스는 클래스 메서드 minBound와 maxBound를 도입하는데, 이는 타입의 최소/최대 원소를 정의해요. 열거형이면 data 선언에 나열된 첫/마지막 생성자가 경계예요. 생성자가 하나뿐인 타입이면 생성자를 성분 타입들의 경계에 적용해요. 예를 들어:

data Pair a b = Pair a b deriving Bounded

은 다음 Bounded 인스턴스를 만들어요:

instance (Bounded a,Bounded b) => Bounded (Pair a b) where
    minBound = Pair minBound minBound
    maxBound = Pair maxBound maxBound

11.4 Read와 Show의 파생 인스턴스

Read와 Show의 파생 인스턴스가 자동으로 도입하는 클래스 메서드는 showsPrec, readsPrec, showList, readList예요. 이들은 값을 문자열로 강제하고 문자열을 값으로 파싱하는 데 쓰여요.

showsPrec d x r는 우선순위 수준 d(0~11), 값 x, 문자열 r을 받아 x를 나타내는 문자열을 r에 이어붙인 결과를 돌려줘요. showsPrec는 다음 법칙을 만족해요:

showsPrec d x r ++ s  ==  showsPrec d x (r ++ s)

만약 x의 최상위 생성자의 우선순위가 d보다 작으면 표현이 괄호로 둘러싸여요. 그래서 d가 0이면 결과는 절대 괄호로 둘러싸이지 않고, d가 11이면 항상 괄호로 둘러싸여요(원자 식이 아니라면 말이죠 — 함수 적용은 우선순위 10이라는 걸 기억하세요). 추가 인자 r은 트리 같은 구조를 크기에 대한 이차 시간이 아니라 선형 시간에 출력하는 데 필수예요.

readsPrec d s는 우선순위 수준 d(0~10)와 문자열 s를 받아 문자열 앞에서 값을 파싱하려 시도하고 (파싱된 값, 남은 문자열) 쌍들의 리스트를 돌려줘요. 성공적인 파싱이 없으면 빈 리스트를 돌려줘요. 괄호 없는 중위 연산자 적용의 파싱은 연산자의 우선순위가 d보다 크거나 같을 때만 성공해요. 다음이 성립해야 해요:

(x,"") is an element of (readsPrec d (showsPrec d x ""))

즉 readsPrec는 showsPrec가 만든 문자열을 파싱할 수 있어야 하고, showsPrec가 시작한 값 그대로를 산출해야 해요.

showList와 readList는 객체 리스트를 비표준 표기로 나타내게 해요. 이는 문자열(Char 리스트)에 특히 유용해요. readsPrec는 문자(따옴표로 감싼 문자열만 받음)와 다른 리스트(대괄호 형태 […]만 받음)를 제외한 표준 타입의 유효한 표기라면 무엇이든 파싱해요. 자세한 내용은 9장을 봐요.

show의 결과는 그 타입이 선언된 지점에 효력을 갖는 fixity 선언을 고려할 때, 상수만 포함하는 구문적으로 올바른 Haskell 식이에요. 데이터타입에 정의된 생성자 이름, 괄호, 공백만 포함해요. 레이블 생성자 필드를 쓰면 중괄호·쉼표·필드 이름·등호도 쓰여요. 괄호는 결합성을 무시하고 필요한 곳에만 추가돼요. 줄바꿈은 추가되지 않아요. 모든 성분 타입이 읽을 수 있으면 show의 결과는 read로 읽을 수 있어요(Prelude에 정의된 모든 인스턴스에 해당하지만, 사용자 정의 인스턴스에는 아닐 수 있어요).

Read의 파생 인스턴스는 Show의 파생 인스턴스가 따르는 다음 가정을 만들어요:

  • 생성자가 중위 연산자로 정의되면, 파생 Read 인스턴스는 생성자의 중위 적용만 파싱해요(접두 형태는 안 됨).
  • 결합성은 괄호의 발생을 줄이는 데 쓰이지 않지만, 우선순위는 그럴 수 있어요. 예를 들어: 
    infixr 4 :$
data T = Int :$ T | NT
    이면: 
    show (1 :$ 2 :$ NT) produces the string "1 :$ (2 :$ NT)".
read "1 :$ (2 :$ NT)" succeeds, with the obvious result.
read "1 :$ 2 :$ NT" fails.
  • 생성자가 레코드 구문으로 정의되면, 파생 Read는 레코드 구문 형태만 파싱하고, 게다가 필드는 원래 선언과 같은 순서로 주어져야 해요.
  • 파생 Read 인스턴스는 입력 문자열의 토큰 사이에 임의의 Haskell 공백을 허용해요. 추가 괄호도 허용돼요.

파생 Read와 Show 인스턴스는 일부 용도에 부적합할 수 있어요. 몇 가지 문제로는:

  • 순환 구조는 이 인스턴스로 출력하거나 읽을 수 없어요.
  • 프린터는 공유된 부분 구조를 잃어요. 객체의 출력 표현이 필요보다 훨씬 클 수 있어요.
  • 리더가 쓰는 파싱 기법은 매우 비효율적이어서, 큰 구조를 읽는 것은 꽤 느릴 수 있어요.
  • Prelude에 정의된 타입의 출력을 사용자가 제어할 수 없어요. 예를 들어 부동소수점 숫자의 형식을 바꿀 방법이 없어요.

11.5 예시 (An Example)

완전한 예시로 트리 데이터타입을 봐요:

data Tree a = Leaf a | Tree a :^: Tree a
              deriving (Eq, Ord, Read, Show)

Tree는 열거형도 단일 생성자 데이터타입도 아니므로 Bounded와 Enum에 대한 인스턴스 선언의 자동 파생은 불가능해요. Tree에 대한 완전한 인스턴스 선언은 아래와 같아요. 클래스 메서드 기본 정의의 암묵적 사용에 주목하세요 — 예를 들어 Ord에는 <=만 정의되고 나머지 클래스 메서드(<, >, >=, max, min)는 6.1절의 class 선언에 주어진 기본값으로 정의돼요.

infixr 5 :^:
data Tree a = Leaf a | Tree a :^: Tree a
instance (Eq a) => Eq (Tree a) where
    Leaf m == Leaf n   = m==n
    u:^:v   == x:^:y   = u==x && v==y
    _       == _       = False
instance (Ord a) => Ord (Tree a) where
    Leaf m <= Leaf n   = m<=n
    Leaf m <= x:^:y    = True
    u:^:v   <= Leaf n  = False
    u:^:v   <= x:^:y   = u<x || u==x && v<=y
instance (Show a) => Show (Tree a) where
    showsPrec d (Leaf m) = showParen (d > app_prec) showStr
      where showStr = showString "Leaf " . showsPrec (app_prec+1) m
    showsPrec d (u :^: v) = showParen (d > up_prec) showStr
      where showStr = showsPrec (up_prec+1) u .
                      showString " :^: " .
                      showsPrec (up_prec+1) v
          -- Note: right-associativity of :^: ignored
instance (Read a) => Read (Tree a) where
    readsPrec d r = readParen (d > up_prec)
                     (\r -> [(u:^:v,w) |
                             (u,s) <- readsPrec (up_prec+1) r,
                             (":^:",t) <- lex s,
                             (v,w) <- readsPrec (up_prec+1) t]) r
                  ++ readParen (d > app_prec)
                     (\r -> [(Leaf m,t) |
                             ("Leaf",s) <- lex r,
                             (m,t) <- readsPrec (app_prec+1) s]) r
  where up_prec = 5  -- Precedence of :^:
        app_prec = 10 -- Application has precedence one more than
                      -- the most tightly-binding operator

이 예는 "파생 인스턴스의 예(Figure 11.1)"로, 파생 인스턴스가 생성하는 실제 코드의 형태를 보여주는 완전한 예시예요.

더 알아보기 (Learn more)