제안: container/...: 제네릭 컬렉션 타입 (generic collection types) #80590

설명 (Description)

배경 (Background): Go 컬렉션(Collections) 작업 그룹은 실용주의와 단순함이라는 익숙한 Go의 원칙에 따라, 공통 컬렉션 데이터 구조를 표준 라이브러리(standard library)에 도입할 목적으로 2025년 말에 결성되었습니다. 성씨의 알파벳 순서에 따라, 이 그룹은 Jonathan Amsterdam (@jba), Alan Donovan (@adonovan), Robert Griesemer (@griesemer), Daniel Martí (@mvdan), Roger Peppe (@rogpeppe), Keith Randall (@khr), 그리고 Ian Lance Taylor (@ianlancetaylor)로 구성되어 있습니다. 이제 우리는 결과를 커뮤니티와 공유할 준비가 되었습니다.

이 이슈는 Go 1.28을 위한 새로운 컬렉션 API에 관한 여러 관련 제안을 논의하기 위한 통합 창구(umbrella)입니다. 주제에 대한 높은 수준의 개요를 제시하며, 다양한 구체적인 제안 및 관련 구현 CL(Change Lists)로 연결되는 링크를 제공합니다.

Go는 현재 라이브러리에서 제공하는 컬렉션 타입이 거의 없으며, 처음부터 언어의 내장 슬라이스(slice) 및 맵(map) 타입의 유연성을 강조해 왔습니다. 제공되는 것 중 가장 중요한 것은 우선순위 큐(priority queues)에 사용되는 힙(heap)입니다. 집합(sets)조차도 없으며, 관습적으로 map[T]bool 또는 map[T]struct{}로 표현됩니다. 이진 트리(binary trees)에 기반한 정렬된 맵(Ordered maps)과 집합(sets)은 완전히 부재합니다.

Go 1.18에서 제네릭(generics)이 추가되고 Go 1.23에서 이터레이터(iterators)가 추가된 이후, 라이브러리 정의 타입이 내장 타입과 유사한 사용성(ergonomics)을 달성하는 것이 가능해졌으며, 슬라이스와 맵에 대한 많은 공통 작업들을 라이브러리 함수 호출로 표현할 수 있게 되었습니다. 이 작업은 몇 가지 더 중요한 데이터 타입을 표준 라이브러리에 추가하고, 해당 API 및 향후 추가될 타입들의 API에 대한 관례를 확립하는 것을 목표로 합니다.

제안 (Proposal): 제안된 추가 사항은 다음과 같습니다:

#70471, CL 657296 (go1.27에서 출시됨):

hash/maphash.Hasher: 임의의 데이터 타입에 대해 사용자 정의 해시 함수 (custom hash functions) 및 동등 관계 (equivalence relations)를 표현하기 위한 표준 인터페이스입니다. 이는 map[K]V에서 사용되는 컴파일러 정의 방식과 다를 수 있으며, 키 타입이 비교 가능하지 않은 경우(예: 슬라이스(slice) 또는 맵(map)), 또는 기본 비교가 잘못된 결과를 생성하는 경우(예: types.Identical의 딥 비교(deep comparison) 연산이 필요한 types.Type 값)에 유용합니다. 패키지 문서에는 Bloom 필터에서의 사용 예시가 포함되어 있습니다. - #69559, CL 612217

: container/hash.Map[K,V]: 위에서 언급한 사용자 정의 해시 함수를 사용하는 해시 기반 맵(Map)입니다. - #80584, CL 741160:

container/hash.Set[T]: 동일한 맥락의 해시 기반 셋(Set)입니다. - #69230

, CL 745441: container/set.Set[T]: 요소가 비교 가능한 셋(set)을 위한 표준 데이터 타입입니다. 이는 map[T]struct{}로 투명하게 표현되며, 합집합(Union) 및 교집합(Intersection)과 같은 모든 일반적인 셋 연산을 지원합니다. 이는 map[T]bool 및 map[T]struct{}에 기반한 "레거시(legacy)" 셋보다 편리하며, map[T]bool에서 발생할 수 있는 잠재적인 거짓 값(false values)에 대한 모호함을 방지합니다. 우리는 이것이 대부분의 새로운 Go API에서 표준 셋이 될 것으로 기대합니다. - #77052

, CL 724420: container/mapset: API를 변경할 수 없는 기존 코드에서 레거시 셋을 셋으로서 편리하게 조작하기 위한 헬퍼 함수(Union, Intersection 등) 패키지입니다. 이 함수들은 set.Set의 메서드들과 정확히 병렬적으로 대응됩니다. - #60630

: container/ordered.Map[K,V]: 정렬된 매핑(ordered mapping)입니다. 현재 구현은 균형 이진 트리(balanced binary tree)를 사용하지만, 설계상 반드시 그래야 하는 것은 아닙니다. map[K]V를 생성한 후 키를 정렬하는 일반적인 Go 패턴은 대부분의 경우 성능이 좋지만, 범위 쿼리(range query)가 필요한 경우와 같이 때때로 다른 데이터 구조가 훨씬 더 나은 성능을 발휘합니다. - #77397

: container/heap/v2.Heap: 사용하기 어려울 수 있는 표준 라이브러리의 기존 힙(heap)을 대체하기 위한 제네릭 이진 힙(generic binary heap) API입니다.

우리는 적절한 시기에 삽입 순서가 유지되는 해시 맵 (insertion-ordered hash maps) (#80194) 및 스택 (stacks) 과 같은 추가 제안들을 검토할 것으로 기대합니다.

제안된 모든 데이터 구조의 초기 구현은 API 및 점근적 성능 (asymptotic performance) 기대치를 가능한 한 단순하게 충족하는 것을 목표로 합니다. 상수 인자 (constant factors)를 줄이기 위한 추후 최적화의 기회는 의심할 여지 없이 많겠지만, 이는 제안 프로세스의 범위를 벗어납니다.

새로운 패키지들은 기존의 container 트리 내에 위치하게 되겠지만, Linux의 컨테이너 가상화 (container virtualization) 개념과 혼동되는 것을 피하기 위해 우리는 "컬렉션 (collection)"이라는 용어를 선호합니다.

추상 컬렉션 제약 인터페이스 (Abstract collection constraint interfaces)

새로운 Map 및 Set 타입의 대부분의 메서드는 특정 구체적 표현 타입 (concrete representation type)에 국한되지 않고, 모든 Map 및 Set에 공통적으로 적용됩니다. 그러나 "이진 메서드 문제 (binary method problem)" 때문에 이들이 공통 인터페이스 타입을 실제로 구현하는 것은 아닙니다. 만약 각 set 데이터 타입 S가 func (S) Union(S) S 형태의 Union 메서드를 가진다면, 서로 다른 set 타입의 Union 메서드들은 호환되지 않으므로 공통된 일반 인터페이스를 가질 수 없습니다. 이 추상적인 Set 타입을 표현하기 위해서는 F-bounded 다형성 (F-bounded polymorphism) 또는 재귀적 제약 인터페이스 (recursive constraint interfaces)를 사용해야 합니다.

CL 761460은 container 패키지에 unexported (비공개) 추상 Collection, Set, Map 제약 인터페이스 타입을 추가합니다. 이를 통해 패키지 구현자들은 다양한 구체적인 컬렉션, set 또는 map 타입 전반에서 작동하는 추상 헬퍼 함수(예: ContainsAny, Subset 또는 Arbitrary)를 작성할 수 있습니다. 우리는 높은 수준의 개념을 전달하기 위해 아래에 몇 가지 간략한 설명을 곁들여 이 인터페이스들을 재현하였으나, 이것들은 어떠한 제안의 일부도 아닙니다. 이들은 단지 테스트에서 준수 여부를 보장하는 역할만 합니다. 자세한 내용은 개별 제안을 참조하십시오.

// _AbstractCollection은 *hash.Map, *hash.Set, *ordered.Map 또는 set.Set과 같은
// 요소 E의 컬렉션 C를 모델링합니다.
type _AbstractCollection[E any, C _AbstractCollection[E, C]] interface {
...

현재 이러한 추상 타입(abstract types)들은 외부로 노출되지 않으며(non-exported), 일관성을 보장하기 위해 Go의 관례(conventions)를 문서화하는 용도로만 사용됩니다. 우리는 아직 이들을 공개할 계획은 없으나, 구체적인 컬렉션 타입(concrete collection types)을 다루며 경험을 쌓은 후 향후 릴리스에서 공개할 수도 있습니다. 그동안 사용자들은 이 예시(CL 761460에서 발췌)와 같이 추상 집합(abstract sets)에 대한 제네릭 Take 함수를 구현할 때처럼, 필요에 따라 최소한의 제약 타입(constraint types)을 정의할 수 있습니다:

// _TakeSet은 [Take] 함수에 충분한 집합(set)의 추상화를 정의합니다.
type _TakeSet[E any, S _TakeSet[E, S]] interface {
All() iter.Seq[E]
...

각 인터페이스에 포함되는 메서드 집합에는 어느 정도의 임의성(arbitrariness)이 존재합니다. 어떤 데이터 구조의 경우, 특정 메서드가 더 효율적인 특화 구현(specialized implementation)을 가능하게 합니다. 하지만 가능한 모든 연산을 인터페이스에 추가한다면, 구현자(implementor)에게 가해지는 부담이 지나치게 커질 것입니다.

예를 들어, Set 인터페이스에 Subset(Set) bool 메서드를 포함해야 할까요, 아니면 Take 예시처럼 Subset을 추상 집합에 대한 제네릭 연산으로 작성해야 할까요? 정렬된 집합(Ordered sets)은 두 피연산자의 범위가 서로소(disjoint)일 때 Subset 테스트를 빠르게 거부할 수 있지만, 그럼에도 불구하고 일반적인 경우 Subset 테스트는 여전히 통상적으로 O(n)이므로, 우리는 인터페이스에서 Subset을 제외하기로 결정했습니다. 반면, Set과 Map 인터페이스에는 DeleteFunc를 유지했는데, 이는 이 메서드가 없으면 트리의 각 요소를 조건부로 삭제할 때 점근적 성능(asymptotically)이 O(n) 대신 O(n log n)으로 더 나빠지기 때문입니다.

특정 메서드 집합에 대한 확정을 미룸으로써, 우리는 실제 사례를 통해 배울 수 있습니다. 어쩌면 표준 제약 타입(canonical constraint types)을 전혀 공개할 필요가 없다는 사실이 밝혀질 수도 있습니다.

기타 논거 (Miscellaneous rationalizations)

이 문서의 나머지 부분은 현재의 제안 세트로 이어지게 된 수많은 작은 설계 선택 사항 중 몇 가지를 간략하게 언급합니다.

반복적인 조회(lookups)를 피하기 위해 메서드는 가능한 한 많은 정보를 반환합니다. 예를 들어:

• 대부분의 변이(mutation) 메서드는 컬렉션의 크기가 변경되었는지 여부를 보고합니다.
• Map.Set과 Map.Delete는 기존 키가 있다면 해당 키를 반환하며, 기존 키를 제로 값(zero value)과 구별할 수 있도록 불리언(boolean) 값을 함께 반환합니다.
• Get은 불리언을 제공하는 At의 변형입니다. (At은 표현식에서 사용하기 편리하도록 제공됩니다.)

Map.Set은 내장된 map을 따라 동일한 키를 가진 기존 항목을 교체해야 합니다.

Set과 달리, map은 Equal 메서드가 없습니다. map의 값(value)은 비교 불가능(non-comparable)할 수 있기 때문입니다.

기본적인 집합 연산(Intersects, Union 등)은 Set 인터페이스의 일부입니다. 이는 다양한 표현 방식에 걸쳐 효율적인 구체적 구현(concrete implementations)을 가능하게 하기 위함입니다. 비록 이 중 많은 것들이 아래 표에 나타난 것처럼 All, Len, Contains만으로 추상적으로 표현될 수 있지만, 그 경우 성능 측면에서 점근적 비용(asymptotic cost)이 발생할 수 있습니다:

- Union{,With} interface{ All() iter.Seq[E] }
- Intersection interface{ All() iter.Seq[E]; Contains(E) bool; Len() int }
- IntersectionWith interface{ Contains(E) bool }
...

Set.{Take, Arbitrary, Subset, Superset}와 같은 보조 연산들은 인터페이스에서 제거되었으며, 추상 집합 인터페이스를 사용하는 제네릭 연산으로 표현되었습니다. 이 역시 잠재적인 점근적 성능 비용이 발생할 수 있습니다. DeleteFunc는 유지되었습니다.

Union과 같은 집합 대수(Set algebra) 연산은 순수 함수적(purely functional)이며, 결과를 새로운 집합으로 반환합니다. 각 연산은 왼쪽 피연산자를 변이시키고 결과를 반환하지 않는 -With 변형을 함께 제공합니다. 이 두 변형은 각각 "편의성"과 "할당 효율성(allocation efficient)"을 목적으로 합니다. 우리는 math/big.Int API에서의 경험을 바탕으로, 그리고 실수로 인한 변이(accidental mutation)나 결과 사용을 잊어버릴 위험을 피하기 위해 이들을 하나의 메서드로 통합하는 아이디어를 거부했습니다.

타입 M인 기반 Map[K,V]의 키 집합을 사용하여 Set[K] 추상화를 만족하는 KeySetView[M, K, V] 래퍼(wrapper) 타입을 정의하는 것이 가능합니다. (물론 Set에 요소를 삽입하는 것은 의미가 없으므로 패닉(panic)을 발생시켜야 합니다.)

대칭성을 위해, 각각의 AbstractMap 메서드와 기존 ‘maps’ 패키지에서 제공하는 연산들을 살펴보겠습니다:

• maps.Clear 없음: 내장 함수인 clear(m)이 수행
• AbstractMap.Clone = maps.Clone
• maps.Contains 없음: _, ok = m[k]로 수행되나, 제안(proposal) #67377을 참조할 것
• maps.ContainsAll 없음: for k := range seq { _, ok = m[k], … }를 통해 효율적으로 수행
• maps.Len 없음: 내장 함수인 len(m)이 수행
• AbstractMaps.All = maps.All
• maps.At 없음: m[k]로 수행
• maps.Delete 없음: delete(m, k)로 수행
• maps.DeleteAll 없음: for k = range seq { delete(m, k) }를 통해 효율적으로 수행
• AbstractMaps.DeleteFunc = maps.DeleteFunc
• maps.Get 없음: v, ok = m[k]로 수행
• AbstractMaps.Keys = maps.Keys
• maps.Set 없음: prev, ok = m[k]; m[k] = newval로 수행
• AbstractMap.SetAll = maps.Insert
• AbstractMaps.Values = maps.Values

이 중 5개(Clone, DeleteFunc, All, Keys, Values)는 정확히 병렬적입니다. 한 가지 연산(AbstractMap.SetAll)은 이름이 다릅니다(maps.Insert). 나머지는 모두 내장 연산자(built-in operators)에 의해 수행됩니다.

우리는 maps.{Contains, ContainsAll, DeleteAll}를 추가하는 것을 제안하고 싶을 수도 있습니다. Contains는 표현식 문맥(expression context)에서 _, ok = s[k]보다 더 유용하며, ContainsAll과 DeleteAll은 루프와 불리언 장부 관리(boolean bookkeeping)의 필요성을 없애줍니다.