하스켈 위키 타입 패밀리 번역

타입패밀리를 더 알아볼 겸 번역했는데, 하는 도중에서야 이건 별로 도움이 안 될 것 같다고 깨닫..
그래도 이왕한 거 유종의 미를 거뒀달까요. 나름 애썼지만 읽을 수 있으면 다행이고 오역을 보장 못 합니다;;
그리고 타입 패밀리가 궁금한 거면 여기나 여기를 읽는 게 더 나을지도...

원문 주소: https://wiki.haskell.org/GHC/Type_families

GHC/Type families

연동_indexed 타입 패밀리, 혹은 짧게 타입 패밀리는 자료형의 즉석 오버로딩을 지원하는 하스켈 언어 확장이다. 타입 패밀리는 구체화 시의 타입 인자에 따라 특수화된 형태를 제공하는 다형 타입이다. 타입 패밀리는 타입 클래스와 비슷하다. 타입 클래스로 함수를 오버로딩하듯이 타입 패밀리는 자료형의 오버로딩을 정의하는 데 사용한다. 타입 패밀리는 의존 타입같이 일반화 프로그래밍, 고도로 인자화된 라이브러리 인터페이스 제작, 더 많은 정적 정보를 가진 인터페이스 제작에 유용하다.

타입 패밀리는 두 가지 형태로 지원된다: 데이터 패밀리와 타입 동의어 패밀리. 데이터 패밀리는 data와 newtype 정의의 연동 형태다. 타입 동의어 패밀리는 타입 동의어의 연동 형태다. 둘 다 단독으로 정의하거나, 타입 클래스와 연관_associate시킬 수 있다. 단독으로 정의하는 게 더 일반적이지만, 연관 방식은 타입이 어떻게 사용되는지 더 명확하게 표현하고 더 나은 에러 메시지를 보여준다.

참고: Simon의 let 일반화 블로그 포스트는 타입 패밀리 확장으로 인한 let 일반화 정책의 중요 변경점을 보여준다. 요약하자면 적법한 하스켈 98 코드라도 -XTypeFamilies로 컴파일하면 실패할 수도 있다.

1. 타입 패밀리란 무엇인가?

타입 패밀리의 개념은 타입 이론에서 가져왔다. 타입 이론에서 연동 타입 패밀리는 타입 수준의 부분 함수_{partial function}다. 이 함수를 (type indice라고 부르는) 인자에 적용하면 타입을 얻을 수 있다. 타입 패밀리는 데이터 생성자를 (단순한 타입 시스템처럼) 고정시키거나 (인자에 다형적인 타입처럼) 불투명한 것처럼 다루지 않고 프로그램이 어떤 데이터 생성자에 동작할지를 계산할 수 있게한다.

타입 패밀리가 되려면 타입 클래스 메소드가 일반 함수인 자료형이어야 한다. 기존 다형 자료형과 함수는 정의 하나를 모든 타입 인스턴스에 사용한다. 반면에 타입 클래스와 타입 패밀리는 인터페이스 정의와 복수의 인스턴스 정의를 가질 수 있다. 타입 패밀리 정의는 그 스스로의 kind와 차수_arity나, 필요한 type indice 개수를 지정한다. 인스턴스 정의는 타입 패밀리를 일부 정의역에 대해 정의한다.

타입 패밀리가 기존 다형 자료형과 어떻게 다른지 볼 간단한 예로, 엄격한 리스트 타입을 보자. Char 리스트를 일반적으로 Cons 생성자를 연결해 나타낼 수 있다. () 리스트도 마찬가지로 표현할 수 있지만, () 값은 아무 정보도 주지 않기 때문에 리스트의 길이만 저장하는 게 더 효율적일 것이다. 이건 기존 다형 자료형으론 불가능한데, 데이터 생성자가 리스트 타입 인자에 의존했기 때문이다. 만약 Char라면 리스트는 Cons 생성자로 만들고, ()라면 리스트는 정수 하나로 만들 것이다. 타입 인자에 따라 다른 자료형을 선택하길 원한다. 타입 패밀리를 사용해서 이 리스트 타입을 아래처럼 선언할 수 있다.

-- 리스트 역할 데이터 패밀리 선언
data family XList a

-- Char 리스트 역할 인스턴스 선언
data instance XList Char = XCons !Char !(XList Char) | XNil

-- () 개수 역할 인스턴스 선언
data instance XList () = XListUnit !Int

두 data instance 선언의 우변은 기존 데이터 정의와 똑같다. 사실 data instance 선언은 type instance(나중에 나옴) 선언이 뒤따라오는 data 선언의 축약일 뿐이다. 하지만 같은 다형 자료형에 XList Char와 XList ()에 대한 2개의 인스턴스를 정의한 데 비해 기존 데이터 선언은 완전히 무관한 타입에 대해 정의한다. 최근 나온 튜토리얼에 타입 패밀리 프로그래밍에 관한 심화 예제가 있다.

GADT는 다형 타입 생성자가 타입 인자에 의존한다는 점에서 타입 패밀리와 비슷하다. 하지만 모든 GADT 생성자는 한 곳에서만 정의해야하는 데 비해 타입 패밀리는 확장가능하다. Functional dependencies도 타입 패밀리와 비슷하고, functional dependencies를 쓴 타입 클래스 대부분을 타입 패밀리로도 온전히 표현할 수 있다. 타입 패밀리는 functional dependencies의 관계형 스타일보다 더 타입수준 프로그래밍의 함수형 스타일을 제공한다.

2. 타입 패밀리를 쓸 때 필요한 것은?

타입 패밀리는 -XTypeFamilies 플래그나 {-# LANGUAGE TypeFamilies #-} 프라그마로 켤 수 있는 GHC 언어확장이다. 타입 패밀리를 최초로 안정 지원하는 GHC 버전은 6.10.1이다. (6.8도 초기 일부분이 구현되어 있지만, 불안정하다.) GHC 버그 트래커에서 가능하면 문제를 재현하는 간결한 프로그램을 첨부해 버그 제보를 바란다. 이 언어 확장이나 이 위키 페이지에 대한 질문이나 토론은 GHC 메일링 리스트를 쓰면 된다.

3. 연관된 자료형 예제

예제로, 일반적인 유한 맵의 형태인 Ralf Hinze의 일반화된 트리에를 보자.

3.1. 클래스 선언

인스턴스를 일반화 맵의 키로 쓸 수 있는 타입 클래스를 선언할 것이다.

class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v

이 클래스에서 주목할 부분은 연관된 데이터 패밀리 선언이다. 그 부분이 (여기선 * -> *인) kind 시그니처를 연관된 자료형 GMap k에 제공한다. 메소드가 클래스 정의에서 타입 시그니처를 받는 것과 비슷하다.

주목할 점은 연관 타입 GMap의 첫째 인자 k가 GMapKey 클래스 인자와 일치한다는 점이다. 이건 클래스의 모든 인스턴스에서 연관 자료형^GMap 인스턴스의 모든 첫째 인자가 인스턴스 타입 k와 일치해야 한다는 뜻이다. 대체로, 연관 타입의 타입 인자는 클래스 파라미터의 일부분(멀티 파라미터 타입 클래스의 경우)일 수 있고, 클래스 인자 순서에 구애받지 않는다. 후자의 속성은 연관 자료형이 특정 문맥에서 부분 적용될 때 유용할 수 있다.

둘째 요점은 GMap k가 * -> *, k가 (암묵적으로) *, (인자 없는) 타입 생성자 GMap이 * -> * -> * kind를 가진다는 점이다. 결과적으로, empty, lookup, insert 메소드 시그니처에서 GMap에 인자 두 개를 적용하는 걸 볼 수 있다.

3.2. Int 인스턴스

Int를 일반화 맵의 키로 쓰기 위해, Data.IntMap을 쓰는 인스턴스를 선언한다.

instance GMapKey Int where
  data GMap Int v        = GMapInt (Data.IntMap.IntMap v)
  empty                  = GMapInt Data.IntMap.empty
  lookup k   (GMapInt m) = Data.IntMap.lookup k m
  insert k v (GMapInt m) = GMapInt (Data.IntMap.insert k v m)

연관 타입 GMap의 Int 인스턴스는 그 인자 둘 다를 필요로 하지만, 첫째 인자만 클래스 인자와 같기 때문에 둘째 인자는 타입 변수가 된다. 이전에 말했듯 클래스 인자와 일치하는 모든 연관 타입 인자는 각각의 인스턴스에서 클래스 인자와 동일해야한다. 연관 데이터 선언의 우변이 다른 자료형 선언과 그러하듯.

참고: 현재는 연관 자료형이나 다른 연동 타입에서 GADT 문법을 지원하지 않는다. 이건 근본적인 한계가 아니라 현재 구현의 한계이고, 미래에 나아질 걸 기대해야 한다.

연습삼아, Int 인스턴스로 대응하는 Char 인스턴스를 Char.ord와 Char.chr을 사용해 만들어보자.

3.3. () 인스턴스

기본적인 타입에서 벗어나서, 일반적인 정의는 대개 (), product, sum을 지원한다. GMap의 유닛 인스턴스 정의로 시작해본다:

instance GMapKey () where
  data GMap () v           = GMapUnit (Maybe v)
  empty                    = GMapUnit Nothing
  lookup () (GMapUnit v)   = v
  insert () v (GMapUnit _) = GMapUnit $ Just v

유닛으론, 맵은 그냥 Maybe 값이 된다.

3.4. 곱타입_product과 합타입_sum 인스턴스

다음으로, 순서쌍과 합_Either에 대한 인스턴스를 정의해보자.

instance (GMapKey a, GMapKey b) => GMapKey (a, b) where
  data GMap (a, b) v            = GMapPair (GMap a (GMap b v))
  empty                   = GMapPair empty
  lookup (a, b) (GMapPair gm)   = lookup a gm >>= lookup b
  insert (a, b) v (GMapPair gm) = GMapPair $ case lookup a gm of
            Nothing  -> insert a (insert b v empty) gm
            Just gm2 -> insert a (insert b v gm2  ) gm

instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
  data GMap (Either a b) v                = GMapEither (GMap a v) (GMap b v)
  empty                                   = GMapEither empty empty
  lookup (Left  a) (GMapEither gm1  _gm2) = lookup a gm1
  lookup (Right b) (GMapEither _gm1 gm2 ) = lookup b gm2
  insert (Left  a) v (GMapEither gm1 gm2) = GMapEither (insert a v gm1) gm2
  insert (Right b) v (GMapEither gm1 gm2) = GMapEither gm1 (insert b v gm2)

만약 이 코드의 알고리즘이 생소하다면, Ralf Hinze의 논문을 보는 걸 제안한다. 이 두 인스턴스에서 연관 타입에 관한 딱 하나 새로운 점은 인스턴스가 문맥 (GMapKey a, GMapKey b)을 가지고 있단 것이다. 그 결과, 연관 타입 선언 우변은 a와 b 키 타입에 대해 GMap을 재귀적으로 쓸 수 있다. 메소드 정의에서 인스턴스 문맥에 제공된 클래스 메소드를 쓰는 것과 다를 바 없다.

3.5. 일반화 맵 사용

드디어, 일반화 맵을 구축하고 질의하는 코드다:

myGMap :: GMap (Int, Either Char ()) String
myGMap = insert (5, Left 'c') "(5, Left 'c')"    $
   insert (4, Right ()) "(4, Right ())"    $
   insert (5, Right ()) "This is the one!" $
   insert (5, Right ()) "This is the two!" $
   insert (6, Right ()) "(6, Right ())"    $
   insert (5, Left 'a') "(5, Left 'a')"    $
   empty
main = putStrLn $ maybe "Couldn't find key!" id $ lookup (5, Right ()) myGMap

3.6. 코드 다운로드

만약 위키에서 이 예제를 복사하지 않고 실행하고 싶다면, GHC 테스트 슈트의 GMap 소스를 받으면 된다.

4. 데이터 패밀리의 자세한 정의

데이터 패밀리는 형태가 두 가지다.
1. 최상위에서 정의되거나
2. 타입 클래스 안에서 연관 타입으로 나올 때

전자가 더 일반적인데, type indices가 클래스 파라미터와 일치하지 않아도 되기 때문이다. 하지만, 후자는 더 구조적인 코드와 (대개 실수로) 일부 타입 인스턴스를 빠뜨렸을 때 더 나은 컴파일러 경고를 생성한다. 아래에서 기본적으로 최상위 정의 형태를 논의할 거고 그 다음으로 연관 타입 형태에 추가되는 제약을 다룰 것이다.

4.1. 패밀리 선언

연동 데이터 패밀리는 아래같은 시그니처로 시작한다.

data family GMap k :: * -> *

이 family 키워드가 패밀리 선언을 일반 data 선언과 구별한다. 마지막 kind 표기는 생략가능하고 기본값은 *이다. 예로는

data family Array e

이름있는(named, 이하 유명) 인자를 kind 시그니처로 대체할 수도 있다. GADT 선언처럼 유명 인자는 선택사항이고, 고로 위 Array 선언은 아래와 동일하다.

data family Array :: * -> *

4.1.1. 연관 패밀리 선언

타입 클래스의 일부로서 데이터 패밀리를 선언할 땐, family 키워드를 안 쓴다. 이런 경우 GMap 선언은 아래같이 된다.

class GMapKey k where
  data GMap k :: * -> *
  ...

반면 최상위 선언에선 type indice로 사용할 모든 클래스 파라미터엔 유명 인자를 써야 한다. 더욱이, 인자 이름은 클래스 파라미터여야 한다. 각 클래스 파라미터는 연관 타입마다 하나까지만 쓸 수 있고 클래스 선언의 순서와 달라도 된다. 다시 말하면 data 선언의 유명 타입 파라미터는 클래스 변수 부분집합의 순열이어야 한다.

아래는 허용 예다:

class C a b c where { data T c a :: * }  -- 가능
class C a b c where { data T a a :: * }  -- 불가: 변수 반복
class D a where { data T a x :: * }      -- 불가: x가 클래스 변수가 아님
class D a where { data T a :: * -> * }   -- 가능

4.2. 인스턴스 선언

data와 newtype 패밀리 인스턴스 선언은 일반 data와 newtype 선언을 빼다박았다. 두 가지 차이는 data나 newtype 다음에 instance가 나오고 타입 인자로 불변 타입을 쓸 수 있지만, forall 타입이나 타입 동의어 패밀리는 쓸 수 없다는 점이다. 하지만 대개 데이터 패밀리는 타입 파라미터로 넣을 수 있고, 타입 동의어도 완전 적용된 상태에 허용되는 타입으로 확장하는 한 허용된다. 이건 클래스 인스턴스 파라미터로 타입 동의어가 나올 때의 요구사항과 같다. 예를 들어, GMap의 Either 인스턴스는

data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)

위 코드 선언은 인스턴스 선언을 딱 하나만 가지고 있다. 보통 인스턴스 선언은 여러 번 할 수 있다.

data와 newtype 인스턴스 선언은 적절한 패밀리 선언이 범위_scope 안에 있어야만 유효하다. 클래스 인스턴스가 클래스 선언을 볼 수 있어야 하는 것과 같다. 더욱이 각각의 인스턴스 선언은 그 패밀리 선언에 지정된 kind와 일치해야 한다. 즉 인스턴스 선언의 파라미터 개수가 패밀리의 kind로 추정한 arity와 일치해야 한다. 데이터 패밀리는 data 키워드로 선언해야 하지만, 인스턴스는 data나 newtype중 어느걸로 선언해도 상관 없다.

타입 패밀리를 최상위 선언으로 정의했어도, 패밀리 인스턴스마다 다른 연산을 하는 함수는 타입 클래스 메소드로 정의해야 한다. 즉, 아래는 불가능하다:

data family T a
data instance T Int  = A
data instance T Char = B
nonsense :: T a -> Int
nonsense A = 1             -- 오류: 이하 두 줄은...
nonsense B = 2             -- 타입 에러를 일으킨다.

GADT_{일반화 대수 자료형}의 기능을 고려하면, 위와 같은 정의가 될 법도 하다. 하지만 타입 패밀리는 GADT와 달리 열려있다. 즉 새 인스턴스를 다른 모듈에서도 추가할 수 있다. 다양한 데이터 인스턴스에서 패턴 매칭을 지원하는건 확장 가능한 case문 구축 설계가 필요할 것이다.

4.2.1. 연관된 타입 인스턴스

타입 클래스 인스턴스 안에서 연관된 패밀리 인스턴스를 선언할 때, 패밀리 인스턴스에서 instance 키워드는 뺀다. 그럼 GMap의 Either 인스턴스는 아래가 된다.

instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
  data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
  ...

연관된 패밀리 인스턴스에서 요점은 클래스 파라미터에 일치하는 type indices가 인스턴스 머리에 있는 타입과 같아야 한단 것이다. 여기선 GMap의 첫째 인자인 Either a b가 딱 하나 있던 클래스 인자와 일치한다. 패밀리 생성자에서 클래스 파라미터와 다른 인자는 모든 인스턴스에서 부정 타입이 돼야 한다. 여기선 변수 v를 말한다.

연관 패밀리 인스턴스는 패밀리가 선언된 클래스의 인스턴스 선언 일부로만 나타낼 수 있다. 클래스의 메소드 연관관계와 마찬가지다. 또한 메소드와 마찬가지로 연관 타입 선언은 클래스 인스턴스에선 생략할 수 있다. 연관 패밀리 인스턴스가 없으면, 대응하는 인스턴스 타입이 없는 것이다. 즉 undefined같이 발산하는 식만 쓸 수 있다.

4.2.2. 클래스 파라미터의 범위_scope

멀티 파라미터 타입 클래스에선 연관 패밀리 인스턴스 우변 클래스 파라미터 가시성은 오직 데이터 패밀리의 파라미터에 달렸다. 예제로 간단한 클래스 선언을 보자.

class C a b where
  data T a

두 클래스 파라미터 중 하나만 데이터 패밀리 파라미터로 썼다. 그 결과 다음 인스턴스 선언은 불가능해진다.

instance C [c] d where
  data T [c] = MkT (c, d)    -- 틀림!! 'd'가 범위 안에 없음

데이터 인스턴스 좌변에 없는 타입 변수 d가 우변에 나온다. 이런 데이터 인스턴스는 타입 안전을 해치기 때문에 금지된다.

4.2.3. 패밀리 인스턴스의 타입 클래스 인스턴스

데이터 패밀리의 타입 클래스 인스턴스는 보통 하던대로 정의할 수 있고, 특히 데이터 인스턴스 선언은 deriving 구문을 가질 수 있다. 즉, 아래가 가능하다.

data GMap () v = GMapUnit (Maybe v)
               deriving Show

위는 아래와 동일하다.

instance Show v => Show (GMap () v) where ...

이런 인스턴스는 데이터 패밀리의 특정 인스턴스를 위한 것이지 전체 패밀리를 통틀어 위한 게 아님을 명심하자. 이건 위에서 말한 한 타입 패밀리에 여러 인스턴스를 대상으로 패턴 매칭을 하는 최상위 함수를 정의할 수 없는 이유와 마찬가지 이유에서다. 이것도 확장가능한 case문 구축이 필요할 것이다.

역자 주: instance Show s => Show (GMap s v) 같은 건 안 된다는 것 같음.

4.2.4. 겹치기

한 프로그램에서 쓰는 데이터 패밀리의 인스턴스 선언은 그게 연관됐는지 아닌지를 떠나서 절대 겹칠 수 없다. 타입 클래스 인스턴스완 달리, 일관성 뿐만 아니라, 타입 안전을 위해서이기도 하다.

역자 주: 같은 타입을 대상으로 여러 인스턴스를 선언하는 걸 얘기. 당연한 말.

4.3. 임포트와 익스포트

타입 패밀리와 데이터 생성자의 연관은 기존 data와 newtype 선언의 연관보다 더 유동적이다. 기존엔 임포트나 익스포트 구문에 T(..)는 타입 생성자와 그 선언에 있는 모든 데이터 생성자를 의미했다. 하지만 패밀리 선언은 어떤 데이터 생성자와도 관련이 없다. 반면 패밀리 인스턴스는 데이터 생성자를 지칭한다. 그 결과, 어떤 데이터 생성자가 타입 패밀리하고 연관되느냐는 현재 보이는 그 패밀리의 인스턴스 선언에 달린다. 즉 임포트와 익스포트의 T(..)는 패밀리 생성자와 현재 보이는 모든 데이터 생성자를 지칭한다. 익스포트의 경우엔, 임포트되거나 현재 모듈에 정의된 데이터 생성자가 될 것이다. GMap(GMapEither)처럼 데이터 생성자를 임포트나 익스포트 항목으로 명시하는 경우의 처리도 유사하다.

4.3.1 연관 패밀리

짐작하다시피, 임포트 및 익스포트 항목에서 C(..) 형태는 클래스의 모든 메소드와 연관 타입을 지칭한다. 하지만 연관 타입을 클래스의 하위 항목으로 명시할 땐, 데이터 생성자인지 타입 생성자인지 구분이 불가능하기에 새 문법이 필요하다. 타입을 뜻한다는 걸 분명히 하기 위해 연관 타입 이름 앞에 type 키워드를 붙여야 한다. 예시로 GMapKey 클래스의 하위 요소를 나열하면 GMapKey(type GMap, empty, lookup, insert)가 된다.

4.3.2. 예시

계속 보아온 GMapKey 클래스 예제로, 익스포트 구문과 그 의미를 알아보자.

• module GMap (GMapKey) where...: 클래스 이름만 익스포트한다.
• module GMap (GMapKey(..)) where...: 클래스와 GMap 연관 타입,
  empty, lookup, insert 메소드를 익스포트한다.
• module GMap (GMapKey(..), GMap(..)) where...: 이전과 같지만,
  GMapInt, GMapChar, GMapUnit, GMapPair, GMapEither, 즉
  모든 데이터 생성자도 익스포트한다.
• module GMap (GMapKey(empty, lookup, insert), GMap(..)) where...: 이전과 같다.
• module GMap (GMapKey, empty, lookup, insert, GMap(..)) where...: 이전과 같다.

마지막으로, GMapKey와 GMap 연관 타입을 동시에 지칭하는 GMapKey(type GMap)도 가능하다. 하지만 GMapKey(type GMap(..)) 은 불가능한데, 하위요소 명시는 중첩이 불가능하기 때문이다. GMap의 데이터 생성자를 나타내려면 따로 분리해야 한다.

4.3.3. 인스턴스

패밀리 인스턴스는 클래스 인스턴스처럼 암시적으로 익스포트된다. 하지만 이건 인스턴스의 머리부만이지, 인스턴스가 정의한 데이터 생성자는 해당 사항이 아니다.

5. 연관된 타입 동의어 예제

타입 동의어 패밀리는 functional dependencies의 대안이다. 즉 functional dependency 예제는 타입 동의어 패밀리를 표현하는 데 적합하다. 사실 functional dependencies의 관계형 표기를 표현식 표기로 바꾸기에 이름과 달리 타입 패밀리가 functional dependencies를 표현하는 더 함수적인 방법이다. 즉 타입에 관한 함수를 관계가 아니라 함수로 표현한다.

5.1. class 선언

아래는 Mark Jones의 functional dependencies 논문에서 가져온 예제다.

class Collects e ce | ce -> e where
  empty  :: ce
  insert :: e -> ce -> ce
  member :: e -> ce -> Bool
  toList :: ce -> [e]

연관 타입 동의어로는 아래처럼 된다.

class Collects ce where
  type Elem ce
  empty  :: ce
  insert :: Elem ce -> ce -> ce
  member :: Elem ce -> ce -> Bool
  toList :: ce -> [Elem ce]

멀티 파라미터 타입 클래스 대신에, 단일 파라미터 클래스를 쓰고 e 파라미터는 연관 타입 동의어 Elem ce로 바뀌었다.

5.2. instance

인스턴스도 마찬가지로 바뀐다. 파라미터 2개인 클래스의 인스턴스는

instance Eq e => Collects e [e] where
  empty           = []
  insert e l      = (e:l)
  member e []     = False
  member e (x:xs)
    | e ## x      = True
    | otherwise   = member e xs
  toList l        = l

의존 타입 파라미터가 연관 타입 인스턴스 선언으로 바뀐 단일 파라미터 클래스의 인스턴스로 바뀐다.

instance Eq e => Collects [e] where
  type Elem [e]   = e
  empty           = []
  insert e l      = (e:l)
  member e []     = False
  member e (x:xs)
    | e x      = True
    | otherwise   = member e xs
  toList l        = l

5.3. 일반화 컨테이너 사용

Functional Dependencies로 아래 코드를 사용했었다.

sumCollects :: (Collects e c1, Collects e c2) => c1 -> c2 -> c2
sumCollects c1 c2 = foldr insert c2 (toList c1)

반면 연관 타입 동의어를 쓰면 아래가 된다.

sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2
sumCollects c1 c2 = foldr insert c2 (toList c1)

6. 타입 동의어 패밀리의 자세한 정의

타입 패밀리는 (1) 최상위에서 정의하거나 (2) 타입 클래스 안에 나오는 (이 경우를 연관 타입 동의어라고 부른다) 두 가지 경우가 있다. 전자는 type-indices가 클래스 파라미터와 일치해야하는 조건이 없어 더 일반적이고, 후자는 더 깔끔한 코드와 실수로 인스턴스를 빠뜨렸을 때 더 나은 컴파일러 경고를 생성한다. 이제부터 최상위 형태를 먼저 설명하고 그 다음으로 연관 타입에 추가되는 제약사항을 다루겠다.

6.1. 패밀리 선언

연동 타입 패밀리는 아래같은 시그니처로 선언한다.

type family Elem c :: *

family 키워드가 패밀리 선언과 기존 타입 선언을 구별한다.
kind 표기는 생략 가능하고 기본값은 *다. 예를 들어

type family Elem c

파라미터를 kind 시그니처로 대체할 수도 있다. 타입 패밀리 선언의 파라미터 개수를 우리는 차수_arity라고 부르고, 타입 패밀리를 쓰는 경우 그 차수만큼은 무조건 채워야 한다. 이 요구조건이 기존 타입 동의어와 다른 부분이고 타입 패밀리의 kind만으론 패밀리의 차수를 알 수 없다는 걸 의미한다. 마찬가지로 보통, 타입 패밀리 적용이 잘 됐는지 확인하기도 충분치 않다. 예를 들어 다음 선언에서

type family F a b :: * -> *   -- F의 차수는 2다.
                              -- 하지만 전체 kind는 * -> * -> * -> *다.

위 선언을 사용할 때 아래는 바른 타입 혹은 잘못된 타입의 예다.

F Char [Int]       -- 통과! Kind: * -> *
F Char [Int] Bool  -- 통과! Kind: *
F IO Bool          -- 불가: 첫째 인자의 kind 불일치
F Bool             -- 불가: 인자 부족

최상위 타입 패밀리는 열려있거나 닫혀있을 수 있다. (연관 타입 패밀리는 항상 열려있다.) 닫힌 타입 패밀리는 정의가 한 곳에 몰려있고 확장이 불가능하다. 반면 열린 패밀리는 인스턴스를 다른 모듈에 퍼뜨릴 수 있다. 닫힌 패밀리의 장점은 그 정의를 패턴매칭 함수정의처럼 순서대로 시도한다는 것이다.

type family G a where
  G Int = Bool
  G a   = Char

위 정의로 G Int는 Bool이 된다. G Double은 Char가 된다. 닫힌 타입 패밀리에 대한 정보는 여기를 보자.

6.1.1. 연관 패밀리 선언

타입 클래스의 일부로 타입 패밀리를 선언하면 family 키워드를 뺀다. 위에서 했던 Elem선언은 다음이 된다.

class Collects ce where
  type Elem ce :: *
  ...

연관 데이터 선언의 경우와 똑같이 유명 타입 파라미터는 클래스 파라미터 부분집합의 순열이어야 한다. 아래는 예제다.

class C a b c where { type T c a :: * }   -- O
class D a where { type T a x :: * }       -- X: x가 클래스 파라미터가 아님
class D a where { type T a :: * -> * }    -- O

6.2. 타입 인스턴스 선언

열린 타입 패밀리의 인스턴스 선언은 기존 타입 동의어 선언과 흡사하다. 딱 두 가지 차이는 type 키워드 뒤에 instance가 따라온단 것과 타입 인자로 고정 타입을 쓸 수 있지만 forall타입이나 타입 동의어 패밀리는 쓸 수 없단 점이다. 하지만, 데이터 패밀리는 보통 가능하고, 타입 동의어도 완전 적용해서 사용 가능한 타입으로 확장되면야 허용된다. 이것도 데이터 인스턴스 때의 제약사항과 완전히 같다. 예를 들어, Elem의 [e] 인스턴스는

type instance Elem [e] = e

타입 패밀리 인스턴스 선언은 다음 규칙을 지켜야 한다. * 맞는 패밀리 선언이 범위 내에 있어야 한다 - 클래스 인스턴스에 클래스 선언이 보여야 하는 것과 마찬가지. * 인스턴스 선언은 패밀리 선언에서 결정된 kind에 맞아야 한다. * 인스턴스 선언의 타입 파라미터 개수는 패밀리 선언의 타입 파라미터 개수와 일치해야 한다. * 타입 인스턴스의 우변은 반드시 monotype이어야 한다. 즉, forall이 들어갈 수 없다. 또한 일반 포화 타입 동의어 확장 후 패밀리 동의어를 제외하곤 어떤 동의어도 안 된다.

아래는 닫힌 패밀리와 적법, 불법 타입 인스턴스 예제다.

type family F a :: *
type instance F [Int]              = Int         -- 통과!
type instance F String             = Char        -- 통과!
type instance F (F a)              = a           -- 불가: 타입 파라미터에 타입 패밀리가 들어감
type instance F (forall a. (a, b)) = b           -- 불가: 타입 파라미터에 forall 타입이 들어감
type instance F Float              = forall a.a  -- 불가: 우변은 forall 타입에 될 수 없음

type family F2 a where                           -- 통과!
  F2 (Maybe Int)  = Int
  F2 (Maybe Bool) = Bool
  F2 (Maybe a)    = String

type family G a b :: * -> *
type instance G Int            = (,)     -- 불가: 타입 파라미터가 2개여야 함
type instance G Int Char Float = Double  -- 불가: 타입 파라미터가 2개여야 함

6.2.1. 닫힌 패밀리 세부사항_{specification}

ghc 7.8.1 버전부터 포함됨.

역자 주: 이 부분은 그냥 GHC User Manual을 보는 게 낫다. 여기는 번역이 오히려 혼란스러울 수 있고 요는 타입 패밀리 패턴 매칭같은 작업에서 애매하면 안 된다는 내용이다.

닫힌 패밀리를 다룰 땐, 타입 단순화 작업은 단지 일치하는 좌변을 찾아서 우변으로 바꾸는 것보다 어렵게 된다. GHC가 타입 패밀리 치환을 적용할 식을 고르는 덴 두 가지 조건이 있다.

1. 대상에 맞도록 식의 좌변에 변수가 들어가 있고
2. 패밀리의 이전 식 각각에 대해 식의 좌변이 떨어져있거나 선택한 식과 호환되어야 한다.

이제, 떨어져있다와 호환된다를 정의하면
1. 임의의 타입 패밀리 단순화 후에도 둘을 서로 다른 것으로 단순화할 수 없으면 두 타입은 떨어져있다고 한다.
2. 두 식의 좌변이 떨어져있거나 좌변이 애매해도 두 식의 우변이 치환 후에 같아졌을 때 두 식은 호환된다고 한다.

아래는 예제다.

type family F a where
  F Int  = Bool
  F Bool = Char
  F a    = Bool

type family And (a :: Bool) (b :: Bool) :: Bool where
  And False c     = False
  And True  d     = d
  And e     False = False
  And f     True  = f
  And g     g     = g

F에서 2번과 3번끼리를 제외하고 모든 식의 쌍이 호환된다. 1번과 2번은 좌변이 떨어져있기에 호환된다. 1번과 3번도 통합 치환하면 우변이 같아지므로 호환된다. 하지만, 2번과 3번은 두 조건이 안 되기에 호환되지 안는다. 그 결과 GHC는 Bool 타입이 아닌 이상 3번 식을 쓰지 않는다.

And에서 식의 모든 쌍들이 호환되고, GHC가 단순화 과정 중 추가적인 떨어짐여부 체크를 하지 않음을 의미한다.

왜 이것들이 필요할까? 이건 타입 안전의 문제다. 다음 예를 보자.

type family J a b where
  J a a = Int
  J a b = Bool

GHC가 두 변수의 타입이 달라서 두번째 것을 선택했다고 하자. 문제는 이 변수가 나중에 같은 값으로 변해서 첫번째 것이 선택될 수도 있는 것이다. 이런 unsafeCoerce를 발생시키는 모순은 인정할 것이다.

더 안 좋은 건, GHC는 부등_inequality의 개념이 없기 때문에 이전 패턴을 쓸 수 없고, 틀린 GADT 패턴을 타입 추론에 쓰게되는 점이다. 예제로

data G :: * -> * where
 GInt  :: G Int
 GBool :: G Bool

type family Foo (a :: *) :: * where
 Foo Int = Char
 Foo a   = Double

bar :: G a -> Foo a
bar GInt  = 'x'
bar _     = 3.14

마지막 줄은 타입 체크에 실패하는데, 타입 변수 a가 Int가 될 수 없단 게 명백한데도 GHC는 모르기 때문이다. 이걸 고치는 보편타당한 방법은 부등 힌트를 GHC에 추가하는 거지만, 이건 큰 작업이고 이런 수정을 가할 만한 가치가 있는 건지 아직 모른다.

6.2.2. 연관 타입 인스턴스

타입 클래스 인스턴스 안에서 연관 패밀리 인스턴스를 선언할 땐
instance 키워드를 뺀다. 그 결과 Elem의 [e]인스턴스는 아래가 된다.

instance (Eq (Elem [e])) => Collects ([e]) where
  type Elem [e] = e
  ...

연관 패밀리 인스턴스에서 요점은 클래스 파라미터에 대응하는 type indexes가 인스턴스 선언 머리에 있는 타입이랑 같아야 한단 것이다. 여기선 유일한 클래스 파라미터인 [e]를 말한다.

연관 패밀리의 인스턴스는 패밀리가 선언된 클래스의 인스턴스 선언 일부로서만 나올 수 있다 - 클래스 메소드를 선언하는 방법과 마찬가지다. 또 하나 마찬가지인 건 연관 타입 선언은 인스턴스 선언에선 생략 가능하단 점이다. 만약 인스턴스를 생략하면, 해당하는 인스턴스 타입이 없게되고, undefined 같이 발산하는 식만 클래스의 타입으로 간주된다.

6.2.3. 겹치기

한 프로그램에서 열린 타입 패밀리의 인스턴스 선언 각각은 위에 나온 형식대로 호환되어야 한다. 타입 패밀리가 연관됐건 아니건간에 그래야 한다. 일관성 뿐만 아니라, 타입 안전을 위해서이기도 하다.

아래는 어떤 조건에서 겹침이 가능한지 보여주는 예제다.

type instance F (a, Int) = [a]
type instance F (Int, b) = [b]   -- 겹침 허용

type instance G (a, Int)  = [a]
type instance G (Char, a) = [a]  -- 겹침 불가: [Char] /= [Int]

6.2.4. 추론 가능성

타입 패밀리 타입 추론이 가능하다고 보장하기 위해서, 타입 인스턴스 선언에 추가적인 제약이 많이 필요하다. (Type Checking with Open Type Functions의 Definition 5 (Relaxed Conditions)을 참고하라). 인스턴스 선언은 다음과 같은 일반형을 가진다.

type instance F t1 .. tn = t

t에 (G s1 .. sm)를 넣어 타입 패밀리를 사용할 때
1. s1 .. sm로 타입 패밀리 생성자를 쓸 수 없고,
2. s1 .. sm의 전체 심볼 개수(자료형 생성자와 타입 변수)는
반드시 t1 .. tn안의 것보다 적어야 하고,
3. 특정 타입 변수 a는 s1 .. sm 안에 최대 t1 .. tn에서 나온만큼만 나올 수 있다.

이 조건은 쉽게 검사할 수 있고 타입 추론이 반드시 끝남을 보장한다. 하지만, 하지만 이 조건도 a ~ [F a]같이 고리 상등_{loopy equalities}이라고 부르는 패밀리 데이터 생성자 안에서의 타입 변수 등장 시에는 소용없다. 자세한 내용은 위에 나온 논문을 참고하라.

만약 -XUndecidableInstances 옵션을 컴파일러에 넘기면, 위에 나온 조건들은 무시되고 타입 패밀리 타입 추론의 종결 보장은 프로그래머 책임이 된다.

6.3. 상등 제약

t1 ~ t2 형태의 t1과 t2 타입이 같다는 걸 의미하는 상등 제약을 타입 문맥에 넣을 수 있다. 타입 패밀리 사용 시 두 타입이 같은지 부분적으로 비교가 불가능하다. 때문에 함수 시그니처 문맥에서 상등 제약을 아래 예제처럼 사용한다.

sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2

이렇게하면 c1과 c2의 원소 타입이 같아야 함을 강제시킨다. 보통 상등 제약을 거는 타입은 임의의 monotype이어야 한다. 즉 고차_higher-rank 타입이건 아니건 한정자가 없어야 사용할 수 있다.

상등 제약은 클래스와 인스턴스 구문에도 넣을 수 있다. 클래스에 넣는 걸로 functional dependencies를 사용한 프로그램을 동의어 패밀리를 사용한 프로그램으로 간단히 바꿀 수 있다. 일반적인 방법은 아래 형태의 클래스 선언을

class C a b | a -> b

아래처럼 바꾸는 것이다.

class (F a ~ b) => C a b where
  type F a

즉, 모든 functional dependency a1 .. an -> b는 타입 패밀리 F a1 .. an와 클래스 상등 제약 F a1 .. an ~ b로 표현할 수 있고, functional dependency라고 명명한 것 뿐이다. 인스턴스에선 클래스 선언 머리와 일치하는 타입 인스턴스를 정의하면 된다. 메소드 시그니처는 영향받지도 않는다.

7. 자주 하는 질문

7.1. 타입 패밀리와 Functional dependencies 비교

Functional dependencies는 타입 패밀리의 일부 영역을 다룬다. 둘은 어떻게 다를까? 이 주제를 다룬 몇몇 글이 있다.

• functional dependencies를 타입 패밀리로 바꾸는 실험: “Functional dependencies vs. type families”
• 둘을 비교하는 GHC trac

7.2. 단사(함수)성_Injectivity, 타입 추론, 모호함

흔한 문제로

type family F a

f :: F a -> F a
f = undefined

g :: F Int -> F Int
g x = f x

이 경우 컴파일러는 g의 정의에 대해 아래 내용으로 불평한다.

Couldn't match expected typeF Int’ against inferred type F a1'

g의 우변을 타입 체킹할 때 GHC는 (f의 타입을 새 타입 변수로 구현해서) 아직 모르는 타입 a1을 넣어 F a1 -> F a1 타입을 얻는다. 이제 GHC는 추론한 타입을 g의 시그니처와 일치시켜본다. a1을 Int와 일치시키면 된다고 말할 수 있다. 맞는 말이지만, 다음 경우는 어떨까?

type instance F Int = Bool
type instance F Char = Bool

그럼 a1을 Char로 가정해도 역시 두 타입을 일치시킬 수 있다. 가능한 해석이 하나가 넘기에, 이 프로그램은 성립되지 않는다.

하지만 (또 혼란스럽게도) g의 타입 시그니처를 생략하면

f :: F a -> F a
f = undefined

g x = f x

GHC는 g :: F a -> F a라고 잘 추론해낸다. 하지만 실제 저 타입 시그니처를 명시할 수는 없다. (이 GHC가 타입을 추론하지만 확인하지 못하는 동작은 분명 이상하다. 필자는 GHC가 타입 시그니처가 있든 없든 다 거부할 수도 있다고 생각한다.)

문제가 뭘까? 핵심은 이거다: F t1 = F t2임을 아는 게 t1 = t2임을 의미하지 않는다. 까다로운 점은 타입 함수 F가 단사함수여야 한다는 조건이 없다는 것이다. F는 두 다른 타입을 같은 타입애 매핑할 수 있다. Maybe같은 단사 타입 생성자는 Maybe t1 = Maybe t2면 t1 = t2임을 알 수 있다. 하지만 단사함수가 아니니 무리다.

문제는 f에서 시작한다. f의 타입은 애매하다. 설령 f의 인자와 결과 타입을 안다한들 a가 무슨 타입이 돼야하는지 알 수 없다. (이런 이유로 f는 애매한 타입을 가졌기에 거부되어야 하고, 아마 나중엔 그렇게 될 것이다.) 이 상황은 타입 클래스에서도 유명하다.

bad :: (Read a, Show a) => String -> String
bad x = show (read x)

bad 호출 시점에 a가 무슨 타입이 돼야 하는지 알 수 없다.

유일한 대책은 애매한 타입을 피하는 것이다. 함수의 시그니처에서
* 모든 타입 변수가 => 뒤에 나오도록 하고,
* 모든 타입 변수가 타입 함수 호출 바깥에서 한번 이상 나오도록 한다.
다른 방법으로, 새 타입을 만들기 때문에 단사 속성을 가지는 데이터 패밀리를 쓸 수도 있다. 다음 코드는 잘 동작한다.

data family F a

f :: F a -> F a
f = undefined

g :: F Int -> F Int
g x = f x

8. 참고자료

• Associated Types with Class. Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. In Proceedings of The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’05), pages 1-13, ACM Press, 2005.
• Associated Type Synonyms. Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming, ACM Press, pages 241-253, 2005.
• System F with Type Equality Coercions. Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. In Proceedings of The Third ACM SIGPLAN Workshop on Types in Language Design and Implementation, ACM Press, 2007.
• Type Checking With Open Type Functions. Tom Schrijvers, Simon Peyton-Jones, Manuel M. T. Chakravarty, Martin Sulzmann. In Proceedings of The 13th ACM SIGPLAN International Conference on Functional Programming, ACM Press, pages 51-62, 2008.
• Fun with Type Functions Oleg Kiselyov, Simon Peyton Jones, Chung-chieh Shan (the source for this paper can be found at http://patch-tag.com/r/schoenfinkel/typefunctions/wiki)