メソッドと型セットの組み合わせ

新しいツリーデータ構造を使用して、要素検索を対数時間で提供する順序付きセットを実装できます。今度は、検索を定数時間で実行する必要があるとしましょう。これを行うために、ツリーと並行して通常のGoマップを維持することを試みるかもしれません：

type OrderedSet[E Comparer[E]] struct {
    tree     MethodTree[E] // 順序での効率的な反復のため
    elements map[E]bool    // （ほぼ）定数時間検索のため
}

func (s *OrderedSet[E]) Has(e E) bool {
    return s.elements[e]
}

func (s *OrderedSet[E]) Insert(e E) {
    if s.elements == nil {
        s.elements = make(map[E]bool)
    }
    if s.elements[e] {
        return
    }
    s.elements[e] = true
    s.tree.Insert(e)
}

func (s *OrderedSet[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        s.tree.root.all(yield)
    }
}

func (n *node[E]) all(yield func(E) bool) bool {
    return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield))
}

しかし、このコードをコンパイルするとエラーが発生します：

invalid map key type E (missing comparable constraint)

エラーメッセージは、マップキーとして使用できるようにするために、型パラメータをさらに制約する必要があることを教えてくれています。comparable 制約は、等価演算子 == と != が定義されているすべての型で満たされる特別な事前宣言制約です。Goでは、これは組み込み map 型のキーとして使用できる型のセットでもあります。

型パラメータにこの制約を追加するには、3つの選択肢があり、それぞれ異なるトレードオフがあります：

1. 元の Comparer 定義に comparable を埋め込む：

   type Comparer[E any] interface {
       comparable
       Compare(E) int
   }

   これには、Tree 型も comparable な型でのみ使用可能になるという欠点があります。一般的に、ジェネリック型を不必要に制限したくありません。

2. 新しい制約定義を追加する：

   type Comparer[E any] interface {
       Compare(E) int
   }
   type ComparableComparer[E any] interface {
       comparable
       Comparer[E]
   }

   これは整然としていますが、API に新しい識別子（ComparableComparer）を導入し、命名は困難です。

3. より制約されたタイプに制約をインラインで追加する：

   type OrderedSet[E interface {
       comparable
       Comparer[E]
   }] struct {
       tree     Tree[E]
       elements map[E]struct{}
   }

   これは少し読みにくくなる可能性があり、特に頻繁に発生する場合はそうです。また、他の場所で制約を再利用することが困難になります。

これらのどれを使用するかはスタイルの選択であり、最終的には個人の好みによります。