유도 인스턴스의 명세

유도 인스턴스의 명세 (Specification of Derived Instances)

data나 newtype 선언에 deriving 절을 붙이면, 그 타입에 대한 인스턴스 선언을 하나하나 손으로 쓰지 않아도 됩니다. 컴파일러가 타입 정의만 보고 클래스의 메서드들을 자동으로 채워 넣어 주는데, 이렇게 자동으로 만들어진 인스턴스 선언을 유도 인스턴스(derived instance) 라고 불러요. 이 장에서는 Haskell 2010 언어 명세가 이런 유도 인스턴스를 어떻게 정의하는지, 클래스별로 하나씩 살펴볼게요.

출처: https://www.haskell.org/onlinereport/haskell2010/haskellch11.html

본문

유도 인스턴스란 무엇인가. 유도 인스턴스는 data 또는 newtype 선언과 함께 자동으로 생성되는 인스턴스 선언입니다. 유도 인스턴스 선언의 몸체는 관련 타입의 정의로부터 구문적으로(syntactically) 파생됩니다. 유도 인스턴스는 컴파일러가 알고 있는 클래스, 즉 Prelude나 표준 라이브러리에 정의된 클래스에 대해서만 만들 수 있습니다. 이 장에서는 Prelude가 정의한 클래스들의 유도 과정을 설명합니다.

T가 다음과 같이 선언된 대수적 데이터타입(algebraic datatype)이라고 해볼게요:

  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 중 하나다.
각 구성 타입 t_ij에 대해 cx′ ⇒ C t_ij가 성립하는 어떤 문맥 cx′가 존재한다.
C가 Bounded라면, 타입은 열거형(모든 생성자가 nullary여야 함)이거나 생성자가 하나뿐이어야 한다.
C가 Enum이라면, 타입은 열거형이어야 한다.
프로그램의 다른 곳에 T u1 … uk를 C의 인스턴스로 만드는 명시적 인스턴스 선언이 없어야 한다.
데이터 선언에 생성자가 없다면(즉 n = 0일 때) 유도 가능한 클래스가 없다(즉 m = 0).

유도 인스턴스의 관점에서 newtype 선언은 생성자가 하나뿐인 data 선언으로 취급됩니다.

deriving 절이 있으면 각 클래스 C_i에 대해 T u1 … uk의 인스턴스 선언이 자동으로 생성됩니다. 어느 C_i에 대해서든 유도 인스턴스 선언이 불가능하면 정적 오류(static error)가 발생해요. 유도 인스턴스가 하나도 필요 없다면 deriving 절을 생략하거나 deriving () 형태를 쓰면 됩니다.

각 유도 인스턴스 선언은 다음과 같은 형태를 가집니다:

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

여기서 d는 C_i와 T의 데이터 타입 선언에 따라 자동으로 파생됩니다(이 절의 나머지에서 설명할 거예요).

문맥 cx′는 위의 조건 (2)를 만족하는 가장 작은 문맥입니다. 상호 재귀적인 데이터 타입의 경우, 컴파일러는 이를 계산하기 위해 고정점(fixpoint) 계산을 수행해야 할 수도 있어요.

이제 유도 가능한 각 Prelude 클래스에 대한 유도 인스턴스의 세부 내용을 살펴볼게요. 이 변환들에서 사용하는 자유 변수와 생성자는 항상 Prelude가 정의한 것들을 가리킵니다.

11.1 `Eq`와 `Ord`의 유도 인스턴스

Eq와 Ord의 유도 인스턴스가 자동으로 도입하는 클래스 메서드는 (==), (/=), compare, (<), (<=), (>), (>=), max, min입니다. 뒤의 일곱 연산자는 주어진 생성자 집합에 대해 자신의 인자를 사전식(lexicographically)으로 비교하도록 정의되는데, 데이터타입 선언에서 앞에 나온 생성자가 뒤에 나온 생성자보다 작은 것으로 취급됩니다. 예를 들어 Bool 데이터타입의 경우 (True > False) == True가 성립합니다.

유도된 비교는 항상 생성자를 왼쪽에서 오른쪽으로 순회합니다. 다음 예들이 이 성질을 보여줘요:

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

Eq와 Ord 클래스의 모든 유도 연산은 두 인자 모두에 대해 엄격(strict) 합니다. 예를 들어 False <= ⊥는 ⊥입니다. False가 Bool 타입의 첫 생성자임에도 그렇죠.

11.2 `Enum`의 유도 인스턴스

Enum 클래스의 유도 인스턴스 선언은 열거형(생성자가 모두 nullary인 데이터 타입)에 대해서만 가능합니다.

nullary 생성자들은 왼쪽에서 오른쪽으로 0부터 n − 1까지의 인덱스로 번호가 매겨진다고 가정합니다. succ와 pred 연산자는 각각 이 번호 체계에서 어떤 값의 후속(successor)과 이전(predecessor) 값을 돌려줍니다. 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 함수는 우선순위(precedence) 수준 d(0부터 11까지의 숫자), 값 x, 그리고 문자열 r을 받습니다. x를 표현한 문자열 뒤에 r을 이어 붙인 문자열을 돌려주죠. showsPrec는 다음 법칙을 만족합니다:

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

x 안의 최상위 생성자의 우선순위가 d보다 작으면 표현이 괄호로 둘러싸입니다. 따라서 d가 0이면 결과가 절대 괄호로 둘러싸이지 않고, d가 11이면 원자 표현(atomic expression)이 아닌 한 항상 괄호로 둘러싸입니다(함수 적용은 우선순위 10이라는 점을 기억하세요). 추가 인자 r은 트리 같은 구조를 트리 크기의 제곱에 비례하는 시간이 아니라 선형 시간에 출력해야 할 때 필수적입니다.

readsPrec d s 함수는 우선순위 수준 d(0부터 10까지의 숫자)와 문자열 s를 받아, 문자열의 앞부분에서 값을 파싱하려 시도하고 (파싱된 값, 남은 문자열) 쌍들의 리스트를 돌려줍니다. 파싱이 성공하지 못하면 돌려주는 리스트는 비어 있어요. 괄호로 묶이지 않은 중위(infix) 연산자 적용의 파싱은 연산자의 우선순위가 d 이상일 때만 성공합니다.

다음이 성립해야 합니다:

(x,"")은 (readsPrec d (showsPrec d x ""))의 원소이다

즉 readsPrec는 showsPrec가 만든 문자열을 파싱할 수 있어야 하고, showsPrec가 시작했던 바로 그 값을 돌려줘야 합니다.

showList와 readList는 객체의 리스트를 비표준 표기(non-standard denotations)로 표현할 수 있게 해줍니다. 이는 특히 문자열(즉 Char의 리스트)에서 유용해요.

readsPrec는 표준 타입들의 유효한 표현을 파싱할 수 있습니다. 단, 문자열은 따옴표로 묶인 형태만 받아들이고, 다른 리스트는 대괄호 형태 [ … ]만 받아들입니다. 자세한 내용은 9장을 참고하세요.

show의 결과는 타입이 선언된 지점에 적용되는 fixity 선언들을 고려할 때 상수만을 포함하는 구문적으로 올바른 Haskell 표현식입니다. 데이터 타입에 정의된 생성자 이름, 괄호, 공백만을 포함하죠. 레이블이 달린 생성자 필드를 사용하면 중괄호, 쉼표, 필드 이름, 등호도 함께 쓰입니다. 괄호는 필요한 곳에만 추가되며 결합성(associativity)은 무시됩니다. 줄바꿈은 추가되지 않아요. 모든 구성 타입이 읽을 수(파싱할 수) 있다면 show의 결과는 read로 읽을 수 있습니다. (이것은 Prelude에 정의된 모든 인스턴스에 대해 성립하지만, 사용자 정의 인스턴스에 대해서는 성립하지 않을 수 있어요.)

Read의 유도 인스턴스는 다음 가정을 하는데, Show의 유도 인스턴스는 이 가정을 따릅니다:

생성자가 중위 연산자로 정의된 경우, 유도된 Read 인스턴스는 생성자의 중위 적용(prefix 형태가 아닌)만 파싱합니다.
결합성은 괄호 발생을 줄이는 데 사용되지 않지만, 우선순위는 그럴 수 있습니다. 예를 들어 다음이 주어졌을 때:

  infixr 4 :$

  data T = Int :$ T  |  NT

그러면:
show (1 :$ 2 :$ NT)는 문자열 "1 :$ (2 :$ NT)"를 만들어 냅니다.
read "1 :$ (2 :$ NT)"는 성공하며, 당연한 결과를 돌려줍니다.
read "1 :$ 2 :$ NT"는 실패합니다.
생성자가 레코드 구문(record syntax)으로 정의된 경우, 유도된 Read는 레코드 구문 형태만 파싱하며, 게다가 필드는 원래 선언과 같은 순서로 주어져야 합니다.
유도된 Read 인스턴스는 입력 문자열의 토큰 사이에 임의의 Haskell 공백을 허용합니다. 추가 괄호도 허용됩니다.

유도된 Read와 Show 인스턴스는 어떤 용도에는 적합하지 않을 수 있어요. 몇 가지 문제점은 다음과 같습니다:

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

11.5 예제 (An Example)

완전한 예로 하나의 트리 데이터타입을 생각해볼게요:

  data Tree a = Leaf a | Tree a :^: Tree a

       deriving (Eq, Ord, Read, Show)

Bounded와 Enum의 인스턴스 선언은 자동으로 유도할 수 없습니다. Tree가 열거형도 아니고 단일 생성자 데이터타입도 아니기 때문이에요. Tree의 완전한 인스턴스 선언은 그림 11.1에 나와 있습니다. 클래스 메서드의 기본 정의(default) 가 암묵적으로 사용된다는 점에 주목하세요 — 예를 들어 Ord에서는 <=만 정의되고, 나머지 클래스 메서드들(<, >, >=, max, min)은 그림 6.1에 나온 클래스 선언에 주어진 기본값으로 정의됩니다.

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



up_prec  = 5    -- Precedence of :^:

app_prec = 10   -- Application has precedence one more than

                -- the most tightly-binding operator

그림 11.1: 유도 인스턴스의 예 (Example of Derived Instances)

더 알아보기 (Learn more)

본문에서 언급한 9장(파싱 세부), 6.1(클래스 선언과 기본 정의), 6.3(deriving 절의 문법)과 함께 읽으면 유도 인스턴스의 전모가 잡혀요.
Eq·Ord의 유도는 사전식 비교, Enum은 번호 매기기, Bounded는 경계 계산, Read·Show는 우선순위 기반 직렬화라는 각기 다른 관심사를 다루므로, 필요할 때마다 해당 절만 다시 봐도 됩니다.
실무에서는 GHC가 이 명세를 확장한 더 넓은 유도 규칙(예: Data, Typeable, 레코드 필드 처분)을 제공하지만, 이 장이 바로 그 규칙들의 근간이 되는 언어 수준의 기준입니다.

유도 인스턴스의 명세