本文へ移動
Hikari 仕様

std:map — 順序付きマップ (SortedMap) と挿入順マップ (InsertionMap)

標準ライブラリモジュール (index.md)。本書中の裸の §N は本書の節を指す。言語の意味論は ../language-spec.md を参照。

import m := "std:map" は 3 つの不透明なマップ型のコンストラクターを持つ namespace object を m に束縛する。3 者は「値をキーにできる」点は共通だが、反復順・キー同一性の基準・可変性が異なる:

  • SortedMap (m.sorted.*) — キーの compare 昇順で反復する。キーは Comparable (language-spec.md §9.4) でなければならない。不変で、変更系メソッドは新値を返す。
  • InsertionMap (m.insertion.*) — 挿入順で反復する。キーは == (構造的値等価、language-spec.md §9.1) で同一性判定し、Comparable である必要はない (任意の値をキーにできる)。不変で、変更系メソッドは新値を返す。
  • ScratchMap (m.insertion.scratch() / m.insertion.build) — InsertionMap と同じキー同一性 (==) を持つが、内部状態が可変な scratch ハンドル。set/remove/update はハンドル自身を前進させ、frozen() で InsertionMap に確定する (§2.3)。

SortedMap と InsertionMap はキー照合が「順序」で決まるか「等価」で決まるかが本質的な違いで、命名もそれを表す (Sorted = compare 昇順・Insertion = 挿入順)。ScratchMap は反復順で言えば InsertionMap 側に属する — 可変な間も挿入順を保ち、確定後も挿入順のまま InsertionMap になる。3 者とも String 識別子に限らず、Int・Tuple・object などをキーにできる。

std:fs / std:term と違い I/O を伴わず、純粋・同期 (Future を返さない)。すべてのコンストラクター・メソッドは即値を返す。

import m := "std:map"

# --- SortedMap: キー compare 昇順 ---
t := m.sorted.of([(1, "a"), (3, "c"), (2, "b")])
t.get(2)        #> Some("b")
t.get(9)        #> None
t.has(3)        #> true
t.keys()        #> [1, 2, 3]            (compare 昇順)
t.length()      #> 3

# 非破壊。t は変わらない
t2 := t.insert(2, "B").remove(1)
t2.entries()    #> [(2, "B"), (3, "c")]
t.entries()     #> [(1, "a"), (2, "b"), (3, "c")]

# --- InsertionMap: 挿入順・任意キー ---
h := m.insertion.of([("class", "card"), ("data-id", "42")])
h.keys()        #> ["class", "data-id"]  (挿入順)
h.insert("class", "card selected").keys()   #> ["class", "data-id"]  (既存キーは位置維持)
h.insert("id", "x").keys()                  #> ["class", "data-id", "id"]  (新規キーは末尾)

# --- ScratchMap: 可変 scratch ハンドル・frozen() で InsertionMap に確定 ---
sc := m.insertion.scratch()
sc.set("class", "card").set("data-id", "42")
sc.get("class")   #> Some("card")
tbl := sc.frozen()   # tbl は InsertionMap。sc は以降使うと Error
tbl.keys()        #> ["class", "data-id"]  (挿入順を保ったまま確定)

以下では import m := "std:map" で束縛したものとして m.sorted.of / m.insertion.of / m.insertion.scratch 等で記す。

1. record との違いと 3 型の使い分け

キーで値を引く辞書は言語の値ではなく、このモジュールが提供する (language-spec.md §7.5)。オブジェクトのスロットは書いた時点で名前が決まっている record のフィールドであり、実行時のキーで引く手段は無い (language-spec.md §3.10 の動的アクセスは Sequence の添字専用)。フィールド名が静的に決まっている構造体は record を、キーが実行時に決まる/識別子として不正な文字を含むものは std:map を使う。

3 型は次のように分かれる:

SortedMap InsertionMap ScratchMap
キー型 任意の Comparable (Int・Float・String・Bool・Unit・compare を持つ object) 任意の値 (Comparable である必要なし) 任意の値
キー同一性 compare (Equal) == (構造のみ・宣言を見ない) 同左
等価 値等価 (§6) 値等価・順序非感応 (§6) 参照同一性
反復順 キーの compare 昇順 挿入順 挿入順
構築後の伸縮 不変。insert/remove が新値を返す 不変。insert/remove が新値を返す 可変。set/remove がハンドルを前進させる

キー昇順で反復したいか (SortedMap)・挿入順を保ちたいか (InsertionMap)・in-place で辞書更新したいか (ScratchMap) で使い分ける。ScratchMap は frozen() で InsertionMap に確定する (§2.3) — std:array の Array が List に対して立つのと同じ二段構えである。

2. キーの制約 — 同一性の基準

SortedMap と InsertionMap はキー同一性の基準が異なる。1 つのマップの中でどちらの基準を使うかは型で決まり、混在しない。ScratchMap は独自の基準を持たず InsertionMap と同じ == に従う (§2.3)。

2.1 SortedMap — Comparable と compare

  • キーは Comparable (language-spec.md §9.4: Int・Float・String・Bool・Unit、compare を持つ不透明値型 (std:decimal の Decimal・std:time の各型)、compare スロットを持つ object) でなければならない。Bytes は原始型だが順序を持たないのでキーにできない (bytes で作った値を sorted のキーに渡すと静的検査が type-mismatch で報告する)。非 Comparable をキーに渡すと静的エラー。sort と同じ規律。
  • キーの同一性は compare で定める: 2 つのキー a, b は a.compare(b) == Equal のとき同一とみなす (== ではない)。順序付き構造として一貫させるための単一基準であり、== のオーバーロード (language-spec.md §9.1) とは独立する。型定義側で compare と == が食い違う場合、マップは compare のみに従う。
  • 1 つのマップのキーは相互に比較可能でなければならない。異型キーの混在 (例: Int キーと String キー) は静的エラー (language-spec.md §9.4)。実用上、1 マップのキーは単一の Comparable 型に揃える。
  • Float をキーにする場合の順序は全順序 (total_cmp 相当、language-spec.md §9.4)。NaN にも定位置があるため壊れない。

2.2 InsertionMap — == と任意キー

  • キーは == (構造的値等価、language-spec.md §9.1) で同一性判定する。Comparable である必要は無く、compare を持たない object もキーにできる。
  • その == は構造だけで見る。 キーが == スロットや compare スロットを宣言していても、キー同一性はそれを呼ばない — SortedMap が compare を呼ぶのと非対称である。索引 (§8) はキーの内容からハッシュを取るので、宣言された等価を呼ぶと「等しいのにハッシュが違う」組を作れてしまい、索引が引き当てられなくなる。宣言した等価でキーをまとめたいときは SortedMap を使う (そちらはキーに compare を要求する)。値の側は普通の == で、宣言があればそれを呼ぶ (§6)。
  • 値には制約なし (String・Bool・任意値)。
  • キー同士は == で比較できれば十分で、異型キーの混在も == が false を返すだけで panic しない (SortedMap と異なり全順序を要求しないため)。

2.3 ScratchMap — ハンドルと確定

ScratchMap のキー同一性は §2.2 の InsertionMap と同じ == で、専用の制約は増えない。

SortedMap / InsertionMap は値そのものである。
ScratchMap は std:array の Array (array.md §2) と対称の可変 scratch ハンドルである。
ScratchMap の == / != は参照同一性であり、同じ内容の別ハンドルは等しくない。
compare / Comparable は持たず、非 Copyable なので std:map / std:set のキーや要素にできない。
内容を比較したい場合は frozen() で InsertionMap に確定する。

ScratchMap は非 Copyable、SortedMap / InsertionMap はCopyable である (../language-spec.md の複製の節)。分かれ目は可変性で、ScratchMap は内部状態が可変なので作り直しても同じものにならず、copy の直接の呼び出しは静的エラーになり spawn / std:parallel の捕獲検査も弾く。確定先の InsertionMap は不変な値なので複製できる。

ScratchMap はAtMostOnce の多重度型である (../language-spec.md の多重度型の節)。frozen が Consuming メソッドで、set / get / remove / update / length は借用である。SortedMap / InsertionMap は不変な値なので多重度を持たない。

ハンドル h の束縛自体は immutable (h = other は再代入エラー)。可変なのは h が指す内部状態 (挿入順のエントリ列とキー索引、§8) だけで、set/remove/update がそれを前進させる。これは Array (array.md §2) や std:random のジェネレーター (random.md §1) と同じ規律で、新しい束縛セマンティクスを増やさない。

h.frozen() は内部状態を InsertionMap に確定して返す (§4)。確定と同時にハンドルは封印 (seal) される — 以降 h のどのメソッドを呼んでも Error。ハンドルの漏れを静的に禁ずるにはランク 2 の多相が要るが、Hikari は higher-rank 多相を持たない (language-spec.md §17.2) ためこれを再現できない。代わりに frozen で封印し、封印後の使用を実行時エラーにする (array.md §2.1 と同じ動的規律)。

h := m.insertion.scratch()
h.set("a", 1)
tbl := h.frozen()  # tbl は InsertionMap。h は封印される
h.get "a"  #> Error (use after frozen)
tbl.get("a")  #> Some(1)

3. namespace とコンストラクター

import m := "std:map" で得られる closed namespace は、sorted / insertion の 2 つのサブ namespace object をそれぞれ slot に持つ (2 型で of/empty が衝突するための分離):

名前 形 効果 意味
sorted.empty m.sorted.empty なし 空の SortedMap (値スロット。呼び出さず参照する)
sorted.of m.sorted.of(pairs) なし (key, value) の 2-Tuple を要素とする List から SortedMap を構築
insertion.empty m.insertion.empty なし 空の InsertionMap (値スロット。呼び出さず参照する)
insertion.of m.insertion.of(pairs) なし (key, value) の 2-Tuple を要素とする List から InsertionMap を構築
insertion.scratch m.insertion.scratch() なし 空の ScratchMap ハンドルを作る
insertion.build m.insertion.build { h | … } なし(ブロックを透過) ハンドルを作りブロックを実行、終了時に frozen() した InsertionMap を返す (scoped 糖衣)

of(pairs): pairs が非 List・要素が非 2-Tuple・(sorted のみ) キーが非 Comparable のとき静的エラー。キー重複は後勝ち (last-wins)。insertion.of の後勝ちは位置維持 (§4 の insert と同じ規律: 先に現れたキーの位置はそのまま、値だけ最後に現れたもので上書き)。

scratch/build を sorted ではなく insertion に置くのは、sorted/insertion の分岐軸が反復順 (§1) であり、ScratchMap が frozen() で確定する先は挿入順の InsertionMap だからである。sorted 側に対応物を置かないのは、今のところ確定先が InsertionMap の 1 種類しか要らないためで (YAGNI)、compare 順を保ったまま可変更新する需要が出れば独立に追加できる。

scratch が値スロットではなく呼び出しなのは、呼ぶたびに独立した内部状態を持つ別のハンドルが要るためである (insertion.empty が値スロットで済むのは、InsertionMap が不変で使い回しても安全だから)。

insertion.build は「ハンドルを作りブロックへ渡して frozen() する」を 1 呼び出しにまとめた安全形で、ハンドルが外へ漏れず、凍結し忘れがない。次のコードはおおよそ同じ効果を持つ展開形である:

h := m.insertion.scratch()
({ h | body })(h)
h.frozen()

insertion.build のブロックパラメーター(h)の型は Borrowed(ScratchMap(k, v)) である(language-spec.md §17.8)。build 自身が最後に呼ぶ frozen() の対象を失わせないためである。

この借用の規律は注釈の有無を問わず静的検査に働く。build の宣言型が持つブロックパラメーターの型が、注釈の無いパラメーターへ流れるためである(static-analysis.md §2「注釈の無いブロックパラメーターへ型を流す」)。h を束縛・コンテナーへ格納・別フローへ捕獲すると cannot-bind-borrowed(static-analysis.md §2.14)になる。実行時の封印(§2.3)はこれとは独立に等しく効く。

m.insertion.build { h: Borrowed(m.ScratchMap(String, Int)) | keep := h }  # cannot-bind-borrowed
m.insertion.build { h | keep := h }  # 同じく cannot-bind-borrowed

SortedMap / InsertionMap / ScratchMap 型は std:map の型メンバーとして export され、型注釈に書ける (language-spec.md §13 のモジュール型 export、time.md §1 と対称)。namespace 名 (sorted/insertion) とは独立にフラットに置かれる: x: m.SortedMap(Int, String) / y: m.InsertionMap(String, Int) / z: m.ScratchMap(String, Int) と修飾参照するか、import { SortedMap, InsertionMap, ScratchMap } := "std:map" で取り出して x: SortedMap(Int, String) と書く。3 者とも不透明型であり内部表現は露出しない (生成は本節のコンストラクター・insert/set 等の派生のみ)。

3.1 型引数 — キー型と値型

3 者はキー型 k と値型 v の 2 つの型引数を持つ型コンストラクターである (language-spec.md §17.2 の List(T) / Option(T) と同じ形): SortedMap(k, v) / InsertionMap(k, v) / ScratchMap(k, v)。get の結果は Option(v)、keys() は List(k)、entries() は List((k, v)) になり、取り出した値に注釈を書き足す必要が無い (§4.2 のシグネチャ表)。

  • 型引数は省略できない。 x: m.InsertionMap は List を裸で書いたときと同じく type-arity-mismatch (static-analysis.md §2)。要素型を問わない位置は InsertionMap(String, Any) と明示で Any を書く (static-analysis.md §2.5 の「暗黙 Any の禁止」と同じ規律で、型注釈では、書き手が明示した Any だけが要素の型を Any にする)。
  • 要素型は of の引数から決まる。 m.insertion.of [("a", 1)] は InsertionMap(String, Int)。sorted.empty / insertion.empty は [] が List(Never) であるのと同じく要素型 Never の空の値で、注釈や最初の insert / merge で確定する。scratch() / build は要素型を引数から取れないので、束縛注釈などの期待型があればそれを要素型にし、値の位置で型引数が決まらなければ、期待型か注釈を要求する静的エラーになる (array.md §3 の collect と同じ規律)。build では期待型がブロックパラメーター h: Borrowed(ScratchMap(k, v)) へ流れ、h.set の引数がその型で検査される。
  • 変性: SortedMap / InsertionMap は不変な値で要素を差し替える経路が無いので、k / v とも共変 (List(T) の要素型と同じ。language-spec.md §17.2)。ScratchMap は set / update がキーと値を書き込むので k / v とも不変 (invariant) — ScratchMap(String, Int) の値は ScratchMap(String, Any) の位置に通らない (static-analysis.md §2.10「可変コンテナー位置の不変性」)。
  • キーの Comparable 境界はシグネチャに置く。 型コンストラクター SortedMap(k, v) そのものの k は無境界である (境界付き型変数は関数型の中でだけ意味を持つ。language-spec.md §17.2)。境界は k を取るシグネチャが持つ — sorted.of の引数と、get / has / insert / remove / merge / compare の受け手 (§4.2)。確実に非 Comparable な型 (List・Tuple・enum のタグ・compare を持たない不透明型) をキーにすると、その位置で type-mismatch (static-analysis.md §3.2 の非充足)。record と関数も、その静的型が Comparable を満たすと示せなければエラーになる。InsertionMap / ScratchMap の k は無境界。
  • 実行時の型照合 (matches と静的に証明できないアスクリプション) はキーと値を走査する。ScratchMap では、先に構築時に確定したキー型・値型の厳密な一致を要求する。空のハンドルでも型引数は失われず、ScratchMap(String, Int) は ScratchMap(Int, String) や ScratchMap(String, Any) に一致しない。不変な InsertionMap / SortedMap は現在のキーと値を共変として照合する。
    束縛・パラメーター・結果型の注釈では照合しない (../language-spec.md §17)。
m.sorted.empty.length()              #> 0
m.sorted.of([])                      #> (空 SortedMap)
m.sorted.of([(1, "a"), (1, "b")])    # キー 1 は後勝ち → { 1: "b" }

m.insertion.empty.length()                     #> 0
m.insertion.of([("a", 1), ("b", 2), ("a", 9)])  # キー "a" は位置維持で値だけ後勝ち → 挿入順 [("a", 9), ("b", 2)]

m.insertion.scratch().length()                 #> 0
(m.insertion.build { h | h.set("x", 1) }).keys()  #> ["x"]

4. メソッド

SortedMap・InsertionMap は同じメソッド顔を持つ。両者の値 t に生えるメソッドはすべて非破壊で、変更系は同じ型の新しい値を返す (元の t は不変)。違いは反復順だけ (sorted = キー昇順 / insertion = 挿入順) だが、いくつかのメソッドは反復順が意味に絡むため注記する。

名前 形 効果 意味
get t.get(k) なし k に対応する値を Some(v)、無ければ None。(sorted のみ) k 非 Comparable は静的エラー
has t.has(k) なし キー k が存在すれば true、無ければ false
insert t.insert(k, v) なし k → v を加えた新値。既存キーは値を上書き。insertion では既存キーは位置維持・新規キーは末尾、sorted は挿入位置を compare で決め直す
remove t.remove(k) なし k を除いた新値。無ければ内容同一の新値
length t.length() なし エントリ数 (Int)
is_empty t.is_empty() なし 空なら true
keys t.keys() なし キーを反復順の List で返す (sorted = compare 昇順 / insertion = 挿入順)
values t.values() なし 値を keys() と対応する順の List で返す
entries t.entries() なし (key, value) 2-Tuple の反復順 List
first t.first() なし 反復順で先頭のエントリを Some((k, v))、空なら None (sorted = 最小キー / insertion = 最初に挿入されたキー)
last t.last() なし 反復順で末尾のエントリを Some((k, v))、空なら None (sorted = 最大キー / insertion = 最後に挿入されたキー)
each t.each { k, v | … } なし(ブロックを透過) 反復順に各エントリへ block を適用 (戻り ())。break / continue を受け、break(value) で抜けたときの値は value (List each と同じ。prelude.md §6)
map t.map { k, v | v' } なし(ブロックを透過) 値を変換した新値 (キー・順序不変)
filter t.filter { k, v | Bool } なし(ブロックを透過) block が true を返すエントリだけの新値 (順序保存)
fold t.fold(init) { acc, k, v | … } なし(ブロックを透過) 反復順の左畳み込み。空なら init
merge t.merge(other) なし other (同じ型) とマージした新値。同一キーは 右 (other) が勝つ (§5)。insertion は左の順を保ち、右の新規キーを末尾追記
to_list t.to_list() なし entries() と同じ (Sequence、prelude.md §6.6 と整合)
compare t.compare(other) なし エントリ列の辞書式順序 (SortedMap のみ。InsertionMap は持たない、§6)

length / is_empty / keys / values / entries / first / last / to_list は zero-arg のため t.length! のように ! 形でも書ける (prelude.md の呼び出し糖衣)。

each / map / filter / fold のブロック内の return は、List のメソッドと同じくメソッドではなく外側の関数から脱出する (language-spec.md §18.2)。

t := m.sorted.of([(1, "a"), (2, "b"), (3, "c")])
(t.map { k, v | v + "!" }).entries()     #> [(1, "a!"), (2, "b!"), (3, "c!")]
(t.filter { k, v | k > 1 }).keys()       #> [2, 3]
t.fold(0) { acc, k, v | acc + k }        #> 6        (キーの和)
t.each { k, v | print(k.inspect! + "=" + v) }     # 1=a / 2=b / 3=c

h := m.insertion.of([("b", 2), ("a", 1)])
h.keys()                                 #> ["b", "a"]         (挿入順)
(h.map { k, v | v * 10 }).entries()      #> [("b", 20), ("a", 10)]   (挿入順を保つ)
(h.filter { k, v | v > 1 }).keys()       #> ["b"]

# Option との合成 (不在のデフォルト値)
t.get(9).or("?")                       #> "?"

4.1 ScratchMap のメソッド

ScratchMap は可変ハンドルであり、§4 冒頭の表 (SortedMap/InsertionMap 共通・すべて非破壊) とは別の表を持つ。ハンドル h に生えるメソッドのうち set/remove/update は内部状態を破壊的に更新する (新しいハンドルは作らない)。すべて封印後 (frozen() 済み、§2.3) は Error。

名前 形 効果 計算量 意味
get h.get(k) なし O(1) k に対応する値を Some(v)、無ければ None
set h.set(k, v) Mut O(1) 上書きまたは新規追加。h 自身を Borrowed(ScratchMap) として返し連鎖可。既存キーは位置維持、新規キーは末尾
remove h.remove(k) Mut O(n) k を削除。無ければ何もしない。h を Borrowed(ScratchMap) として返す
has h.has(k) なし O(1) キー k が存在すれば true
update h.update(k, init) { v | v' } Mut(ブロックを透過) O(1) read-modify-write。k が不在なら init を初期値として block に渡す。h を Borrowed(ScratchMap) として返す
length h.length() なし O(1) エントリ数 (Int)
keys h.keys() なし O(n) キーを挿入順の List で返す
frozen h.frozen() なし O(n) 内部状態を InsertionMap に確定し、ハンドルを封印する (§2.3)

get が Option を返すのは、Array の範囲外添字が呼び出し側のバグとして Error になる (array.md §6) のと違い、ScratchMap ではキーの不在が正常な状態だからである。update が init を取るのは、キーの有無を問わず read-modify-write を 1 呼び出しで書けるようにするためで (不在なら init をブロックへ渡す)、これが無いと has で分岐してから set/update する 2 段構えが必要で、置き換え元の破壊的コードよりかえって冗長になる。

length / keys / frozen は zero-arg のため h.length! のように ! 形でも書ける (prelude.md の呼び出し糖衣)。ScratchMap は merge/map/filter/fold/values/entries/first/last/each/compare を持たない — これらの非破壊系メソッドが要るときは frozen() で InsertionMap に確定してから使う。

set / remove / update の戻りが所有ではなく借用 (Borrowed(ScratchMap)) なのは、これらが受け手を消費しないためである。所有を返すと、消費されていない受け手と合わせて同じ内部状態への経路が 2 本になる (../language-spec.md の多重度型の節)。連鎖 (h.set("a", 1).set("b", 2)) はそのまま書ける一方、戻りを別の名前に束縛したりコンテナーへ入れたり別フローへ捕獲したりすると cannot-bind-borrowed (static-analysis.md §2.14) になる。

h := m.insertion.scratch()
h.set("a", 1).set("b", 2).update("a", 0) { v | v + 10 }
h.get("a")     #> Some(11)
h.get("z")     #> None
h.has("b")     #> true
h.remove("a")
h.keys!        #> ["b"]
tbl := h.frozen()   # tbl は InsertionMap { "b": 2 }。h は以降 Error

4.2 静的なシグネチャ

受け手の型引数 k / v に対する各メソッドの静的型 (hover に出る形。static-analysis.md §2.2 のとおり実引数の照合はこの型に対して行う)。M は受け手と同じ型コンストラクター (SortedMap または InsertionMap)、w は map のブロックの結果型、acc は fold の初期値の型から確定する。

名前 SortedMap(k, v) / InsertionMap(k, v) ScratchMap(k, v)
sorted.of { List(((k: Comparable), v)) | SortedMap(k, v) } —
insertion.of { List((k, v)) | InsertionMap(k, v) } —
sorted.empty / insertion.empty M(Never, Never) ([] と同じ規律。注釈や最初の insert で確定) —
insertion.scratch — {| ScratchMap(k, v) } (同上)
insertion.build — { { Borrowed(ScratchMap(k, v)) | Unit } | InsertionMap(k, v) } (同上)
get { k | Option(v) } { k | Option(v) }
has { k | Bool } { k | Bool }
insert { k, v | M(k, v) } —
set — { k, v | Borrowed(ScratchMap(k, v)) }
remove { k | M(k, v) } { k | Borrowed(ScratchMap(k, v)) }
update — { k, v, { v | v } | Borrowed(ScratchMap(k, v)) }
length {| Int } {| Int }
is_empty {| Bool } —
keys {| List(k) } {| List(k) }
values {| List(v) } —
entries / to_list {| List((k, v)) } —
first / last {| Option((k, v)) } —
each { { k, v | Unit } | Unit } —
map { { k, v | w } | M(k, w) } —
filter { { k, v | Bool } | M(k, v) } —
fold { acc, { acc, k, v | acc } | acc } —
merge { M(k, v) | M(k, v) } —
compare (SortedMap のみ) { SortedMap(k, v) | Ordering } —
frozen — {| InsertionMap(k, v) }

SortedMap の k を取る位置には Comparable 境界が付く — 表の k は SortedMap では (k: Comparable) と読む (sorted.of の引数、get / has / insert / remove の第 1 引数、merge / compare の引数の SortedMap(k, v)。hover にはこの形で出る)。受け手の k が Comparable を満たすと示せなければ、これらの呼び出しは受け手の型引数で落ちる:

x: m.SortedMap(List(Int), String) := m.sorted.empty
x.insert([1], "a")   # type mismatch: receiver of insert expects SortedMap((k: Comparable), v), got SortedMap(List(Int), String)
x.length!           # 出ない — キーを比べないメソッドは境界を見ない

k を比べない length / is_empty / keys / values / entries / first / last / each / map / filter / fold は出ない (キーを渡さない限り、非 Comparable のキー型で注釈した空の map はエラーではない)。InsertionMap / ScratchMap の k は無境界。

insertion.build / each のブロックの結果型は Unit で、その本体の結果は捨てる。
関数型の照合は不変であり、この文脈は関数型の部分型関係を変えない。

ScratchMap の set / update の値は、受け手の v に静的に代入できなければエラーになる
(static-analysis.md §2.10)。
不変な insert / merge でも、型が割れた合流に期待型が無ければ静的エラーになる。
期待型があれば各値をその型に照らす (static-analysis.md §3.1)。

5. merge (マージ)

t.merge(other) は 2 つの同じ型の値をマージした新値を返す。同一キーは 右 (other) が勝つ。

  • 演算子 + はオーバーロードしない (time.md §1 と同方針 — 不透明値型は演算子を増やさず名前付きメソッドで操作する)。マージは merge で行う。
  • other が同じ型 (SortedMap 同士・InsertionMap 同士) でなければ静的エラー (型混在は不可)。
  • SortedMap: 結果のキーは両者の和で、compare 昇順を保つ。
  • InsertionMap: 結果の順序は左 (t) の並びを保ち、右 (other) にしかない新規キーを末尾に追記する。左右の両方にあるキーは左の位置を維持したまま値だけ右のもので上書きされる (insert の位置維持規律と同じ)。
a := m.sorted.of([(1, "a"), (2, "b")])
b := m.sorted.of([(2, "B"), (3, "c")])
a.merge(b).entries()   #> [(1, "a"), (2, "B"), (3, "c")]    (キー 2 は右勝ち)

ha := m.insertion.of([("a", 1), ("b", 2)])
hb := m.insertion.of([("b", 20), ("c", 3)])
ha.merge(hb).entries()   #> [("a", 1), ("b", 20), ("c", 3)]  (左の順を保ち、"b" は右の値・"c" は末尾追記)

6. 等価と順序 (== / compare)

SortedMap・InsertionMap はどちらも 値等価を持つ (time.md §1 の不透明値型と同じ方針)。core の object マップ (String 名キー) と違い、任意の値をキーにとれるのが特徴だが、順序 (compare) を持つのは SortedMap だけ。

  • SortedMap:
    • ==: t1 == t2 は、キー集合が一致 (compare 同一) し、かつ各キーの値が == (language-spec.md §9.1) で等しいとき true。別インスタンスでも内容が同じなら true (構築順に依らない)。
    • compare: エントリをキー昇順に並べた列の辞書式順序で Ordering を返す。< <= > >= がこれを経由して効き、SortedMap を別の SortedMap/OrderedSet のキー/要素にネストできる (集合演算・マップのキーは内部でこの compare を使う)。値の比較は値が Comparable なときのみ意味を持ち、非 Comparable 値を含む compare は静的エラー。
  • InsertionMap:
    • == は順序非感応: 同じ (key, value) 集合であれば、挿入順が異なっていても true。順序 (反復順) は同一性に一切関与しない。キーの突き合わせは §2.2 のキー同一性 (構造のみ) で、値の突き合わせは普通の == (宣言があればそれを呼ぶ) である。
    • compare を持たない。InsertionMap は全順序を持つ必要が無く (v.matches(type Comparable) は false)、< <= > >= は使えない (呼び出せば universal method 不在として静的検査で弾かれる)。並び (挿入順) を検査したいときは == ではなく entries!/keys! (List・順序感応) を使う。
m.sorted.of([(1, "a"), (2, "b")]) == m.sorted.of([(2, "b"), (1, "a")])   #> true   (順不同で構築しても同値)
m.sorted.of([("a", 1)]) == { a := 1 |}                                   #> false  (object マップとは別物)

a := m.insertion.of([("class", "card"), ("id", "x")])
b := m.insertion.of([("id", "x"), ("class", "card")])
a == b            #> true                          (中身一致・並び無視)
a.entries!        #> [("class", "card"), ("id", "x")]  (並びは entries で見る)
b.entries!        #> [("id", "x"), ("class", "card")]

7. エラーモデル

get (SortedMap / InsertionMap / ScratchMap) と first / last は不在を None で返す。
ScratchMap の封印後の使用は呼び出し側のバグとして Error になる
(§2.3)。

以下は静的エラーになる:

  • SortedMap の非 Comparable なキー、および相互に比較できない異型キーの混在
  • of の非 List 引数、または要素が 2-Tuple でない引数
  • merge の相手が同じ型でない (SortedMap に InsertionMap を渡す等)
  • SortedMap.compare の非 Comparable な値

InsertionMap / ScratchMap のキー型には Comparable 境界が無い。

8. 計算量

  • SortedMap: compare 昇順に保った不変 slice で実装する (コピーオンライト)。要素数 n に対し:
    • get / has: O(log n) (二分探索)
    • first / last: O(1) (先頭・末尾への直接添字アクセス)
    • insert / remove: O(n) (不変ゆえ slice をコピー)
    • keys / values / entries / each / map / filter / fold / to_list: O(n)
    • merge: O(m log n + (n+m)) 程度 (m は相手の要素数)
  • InsertionMap: 挿入順を保つ不変 slice で実装する (コピーオンライト)。要素数 n に対し:
    • get / has: O(n) (線形探索。索引は持たない — 不変なので索引を持ち回れず、1 回引くために組めば組む側が O(n) かかって釣り合わない)
    • first / last: O(1) (先頭・末尾への直接添字アクセス)
    • insert / remove: O(n)
    • keys / values / entries / each / map / filter / fold / to_list: O(n)
    • of: O(n) (n は渡した対の数。後勝ちの畳み込みに使い捨ての索引を組む)
    • merge: O(n+m) 程度 (m は相手の要素数。同じく使い捨ての索引で引く)
    • ==: O(n) 程度 (§6 の順序非感応な値等価。同じく使い捨ての索引で引く)
  • ScratchMap: 挿入順 slice + キー索引で実装する (可変)。要素数 n に対し:
    • get / set / has / update: O(1) (索引でスロットへ直接アクセス。ただし下記「索引に載るキー」の限定が付く)
    • remove: O(n) (挿入順の列から詰めるので後続の位置がずれ、索引が持つ位置も直す)
    • keys: O(n)
    • frozen: O(n) (内部状態を InsertionMap へ確定。索引は引き継がない — 確定先は不変で、insert/remove のたびに作り直すことになるため)

SortedMap がハッシュではなく順序 (compare) を採るのは、Hikari が既に compare/Comparable を持ち Hashable を持たないこと、反復順を決定的にできることによる。insert/remove を O(log n) にする平衡木への置き換えは内部実装の最適化余地 (外部契約は変わらない)。

InsertionMap の get が O(n) のままなのに対し ScratchMap の get/set が O(1) になるのは、両者とも索引の要る == キーを持つ点は同じでも、InsertionMap は不変ゆえコピーオンライトで索引を都度作り直すコストを避けているのに対し、ScratchMap は可変ゆえ索引を持ち回ったまま更新できるという違いによる。of/merge/== だけが O(n) 系に乗るのは、これらが1 回の呼び出しの中で何度も引くからで、そこでは組む O(n) を引く回数で割れる。1 回しか引かない get/has では割れない。

索引に載るキー

索引はキーの内容から引く。一方 == の同一性も値の中身で決まるので、中身が後から変わりうる値は索引に載せられない — 載せた時点の内容と実態が食い違い、同じキーで引き直せなくなる。そこでキーを 2 つに分け、載せられるものだけを索引に載せる。

  • 索引に載るキー — 中身の変わりえない値。原始型 (Unit・Bool・Int・Float・String・Bytes・Decimal・時刻の各型)・Tuple・variant・および それらだけを含む List がこれにあたる。同一性が箱の参照で決まる値 (Range ほか) も、参照は変わらないので載る。
  • 索引に載らないキー — 可変スロットを持ちうる object と、内容の同一性が別の規則で決まる値 (InsertionMap・SortedMap・OrderedSet)。これらは位置だけを別の短い列で持ち、線形に突き合わせる。

この 2 つは == で交わらない — 載るキーと載らないキーが等しくなることは無い。したがって探すキーがどちらに属するかで見る先が一意に決まり、索引が「外れて全件走査に落ちる」ことは無い。載らないキーをいくつ格納しても、載るキーの get/set/has/update は O(1) のままである。比例するのは載らないキーでの操作だけで、その本数 (要素数 n ではない) に比例する。

要素数が少ないうちは索引を持たず全件走査する。索引を引く費用 (キーの内容をたどる) が走査より高くつく範囲があるためで、境目の要素数は実装が決める。

この限定はすべて速度だけの話で、返す答えは常に InsertionMap と一致する。 どのキーを使っても同一性の判定結果は変わらない。