std:array — 可変 scratch 配列 (Array)

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

import arr := "std:array" は O(1) で添字更新できる可変 scratch ハンドル Array のコンストラクターを slot に持つ namespace object を arr に束縛する。可変性は Array ハンドルの内部に閉じ込められ、frozen() で immutable List に確定して外へ出す。「中は可変・外は純粋」を 1 つのハンドルに閉じた形である。

std:fs / std:http/client のような外部リソース I/O を伴わず、std:map と同じく 純粋・同期 (Future を返さない)。std:array を import すること自体が「このコードは in-place な添字更新を使う」ことの可視化になる (index.md)。

import arr := "std:array"

# DP テーブルを O(1) 更新で埋め、immutable List として確定する
fact := arr.build(n + 1, 1) { a |
  range(1, n + 1).each { i |
    a.set(i, a.get(i - 1) * i)
  }
}
fact.0          #> 1
fact.length!    #> n+1                 (frozen 後は普通の List)

以下では import arr := "std:array" で束縛したものとして記す。

1. なぜ List ではなく Array か

Hikari の List・タプル・String は不変で、要素の差し替え l.[i] = X はランタイムエラー、長さも生成後に変わらない (language-spec.md §7.4)。要素を変えるには map で新リストを作る。これは通常のコードでは自然だが、任意添字への O(1) 散在書き込みを前提に計算量が成立するアルゴリズム (DP テーブル・グリッド更新・in-place sort・Union-Find・counting sort・Fisher–Yates) では、map 作り直し (各 O(n)) が O(n²) に膨らむ。

Array はこの一点を埋める。List の要素を可変にするのではなく、専用メソッド set で内部 buffer を更新する opaque ハンドルであり、frozen() で List に落とすまで O(1) 更新を許す。

2. モデル — ハンドルと確定

std:array は 2 層からなる。

• コンストラクター (arr.array / arr.empty / arr.from / arr.build / arr.collect) — Array ハンドルを作る。モジュール直下のスロット。
• ハンドル (a) — get/set/swap/update/push/length/frozen を持つ opaque object。型は要素型 e を型引数に持つ Array(e) (§3)。set 等を呼ぶたびに内部状態が前進する。

ハンドル a の束縛自体は immutable (a = other は再代入エラー)。可変なのは a が指す内部 buffer だけで、set/swap/update がそれを前進させる。これは std:random のジェネレーター (random.md §1) と同じ規律で、新しい束縛セマンティクスを増やさない。

Array は値型ではないため ==/compare/Comparable を持たず、std:map/std:set のキーや要素にできない。比較したい/持ち回りたい結果は frozen() で List に確定する。

Array は非 Copyable である (../language-spec.md の複製の節)。内部 buffer が可変で、作り直しても同じものにならないためである。copy は panic し、spawn / std:parallel の捕獲検査も弾く。持ち回りたければ frozen() で List に確定する。

Array はAtMostOnce の多重度型である (../language-spec.md の多重度型の節)。frozen が Consuming メソッドで、get / set / swap / update / length は借用である。確定し忘れは漏れではないので ExactlyOnce にはしない。

2.1 確定 (frozen) と封印

a.frozen() は内部 buffer を immutable List に確定して返す (O(1)。buffer をそのまま List の格納に move する)。静的型は Array(e) の要素型を運んだ List(e) である。確定と同時にハンドルは封印 (seal) される — 以降 a のいずれのメソッドを呼んでも Error。

ハンドルの漏れを静的に禁ずるには「ハンドルの型引数を呼び手が選べない」ランク 2 の多相が要るが、Hikari は higher-rank 多相を持たない (language-spec.md §17.2) ためこれを再現できない。代わりに frozen で封印し、封印後の使用を実行時エラーにするという動的な規律を採る。

a := arr.array(3, 0)
a.set(0, 9)
xs := a.frozen()  # xs は immutable List [9, 0, 0]。a は封印される
xs.0  #> 9

封印を踏む前に、まず多重度型の消費追跡が止める。 frozen は Consuming メソッドなので (§2)、上の続きに a.get 0 と書いた綴りは実行まで進まず use of consumed value 'a' (use-after-consume) (static-analysis.md §2.14) で断られる。封印は追跡が名前を見失う位置のための後詰めである — 確定より前に作った関数リテラルがハンドルを捕獲していると、追跡はその呼びを消費として数えられない。

arr.collect { h |
  h.push(1)
  get0 := {| h.get(0) }   # 確定より前に捕獲する
  h.frozen()
  get0!                     #> Error — Array.get: use after frozen
}

arr.build / arr.collect (§3) はブロックを抜けたところで自分で確定するので、ブロックの中で h.frozen() を呼ぶと同じ封印を build / collect 自身が踏む (Array.build: use after frozen)。確定はどちらか一方が行う。

3. コンストラクター

import arr := "std:array" で得られる closed namespace の slot:

build は次と等価な安全形 — ハンドルが外へ漏れず、凍結し忘れがない:

arr.build(n, init) { h | body }
≒ { _ | a := arr.array(n, init); ({ h | body })(a); a.frozen() }

collect は長さを決めずに始める同じ形である。要素は push で末尾へ足す:

arr.collect { h | body }
≒ { _ | a := arr.empty(); ({ h | body })(a); a.frozen() }

collect は要素型を引数から取れない（build の init にあたるものが無い）ので、要素型は期待型から取る — xs: List(String) := arr.collect { … } と束縛注釈があればブロックパラメーターは h: Borrowed(Array(String)) になり、h.push の引数がその型で検査され、結果は List(String) になる。期待型が無ければ要素型は Any で、結果の静的型は List(Any) になり、無注釈の束縛は implicit-any-binding が注釈を求める (static-analysis.md §2.5)。書き手の手間は今までと同じ（注釈を 1 度書く）で、その注釈がブロックの中まで届くようになる。

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

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

arr.build(3, 0) { h: Borrowed(arr.Array(Int)) | keep := h }  # cannot-bind-borrowed
arr.build(3, 0) { h | keep := h }                       # 同じく cannot-bind-borrowed

Array 型は std:array の型メンバーとして export され、型注釈に書ける (language-spec.md §17 のモジュール型 export、map.md §3 と対称)。h: arr.Array(Int) と修飾参照するか、import { Array } := "std:array" で取り出して h: Array(Int) と書く。不透明型で内部表現は露出しないが、要素型 e を型引数に持つ (Array(e)。language-spec.md §17.2 の List(T) と同じ形の型構築子)。region パラメーター (ST s の s) は持たない — 漏れ防止は §2.1 の実行時封印が担う。

型引数の規律は map.md §3.1 と同じである。

• 型引数は省略できない。 h: arr.Array は type-arity-mismatch。要素型を問わない位置は Array(Any) と明示で書く。
• 要素型は array(n, init) の init・from(list) の要素型から決まる。 empty() と collect は期待型から取る — acc: arr.Array(String) := arr.empty() と束縛注釈を書けば acc.push の引数がその型で検査され、無注釈なら Array(Any) になって implicit-any-binding が注釈を求める。empty() が array(0, init) と別にあるのは、要素型を決める init を置く場所が無いからである。
• e は不変 (invariant) である。 set / push / update が要素を差し替えるので、Array(Int) の値を Array(Any) の位置に通すと広い視点から Int でない値を書き込めてしまう (language-spec.md §17.2 の変性、static-analysis.md §2.10「可変コンテナー位置の不変性」)。
• 実行時の照合は List(T) と同じで、注釈位置では要素を走査して照合する。静的に確実な位置は型消去 (../language-spec.md §17) が照合を消す。

静的なシグネチャ (hover に出る形。実引数の照合はこの型に対して行う):

set / push / update は受け手を破壊的に書き換えるので、引数の値の型が e と確実に非整合なら静的検査が報告する (static-analysis.md §2.10「可変な器への書き込みの要素型照合」。List の push と同じ契約系の規則)。

arr.array(3, 0)  # Array [0, 0, 0]
arr.from [10, 20, 30]  # Array [10, 20, 30]
arr.array(0, 0).frozen()  #> []          (空 Array)
arr.array(-1, 0)  #> Error (n が負)

4. メソッド

Array 値 a に生えるメソッド。set/swap/update は内部 buffer を破壊的に更新する (新しい Array は作らない)。すべて封印後は Error (§2.1)。

length / frozen は zero-arg のため a.length! / a.frozen! のように ! 形でも書ける (prelude.md の呼び出し糖衣)。

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

get/set/swap/update の範囲外添字は不在ではなく呼び出し側のバグなので Option ではなく Error (バグ層、language-spec.md §16.2。長さは既知。List の位置アクセス §7.4 と同規律)。

# in-place quicksort の分割 (swap を使う)
sorted := arr.build(xs.length!, 0) { a |
  xs.each { x, i | a.set(i, x) }
  qsort(a, 0, a.length! - 1)  # a を渡して再帰的に swap
}

# ヒストグラム (update による散在加算)
counts := arr.build(k, 0) { a |
  samples.each { s | a.update s { c | c + 1 } }
}

# 長さが入力次第の組み立て (collect + push)
toks := arr.collect { a |
  src.each { c | a.push(lex c) }
}

5. 多次元

1D のみである。グリッド/行列は flat 配列 + 添字算術で表現する。

# rows × cols のグリッドを 1D に潰す
grid := arr.build(rows * cols, 0) { a |
  a.set(r * cols + c, v)
}
# frozen 後は flat List。2D 形が要れば reshape は呼び側

2D 専用 API (tuple 添字で 1D と綴りを統一する形・2D 専用の別型を足す形のどちらも) は実使用を見てから決める将来枠。現行の 1D シグネチャはどちらの拡張方向にも非破壊で対応できる形にしてある。数値線形代数の Vector/Matrix は不変値型 + 線形代数演算という別物であり、本モジュールには含めない (別の将来モジュール std:linalg 等)。

6. エラーモデル

std:array は Error (バグ層、language-spec.md §16) のみを使う。get の範囲外も含めすべて呼び出し側のバグであり、回復可能な「不在」(Option) は返さない (添字アクセスは長さが既知の前提で行う、List の位置アクセスと同じ規律)。

Error になるもの:

• get/set/swap/update の範囲外添字、または非 Int 添字
• array(n, …) の n が負数または非 Int
• from(list) の引数が非 List
• 封印後 (frozen 済み) のハンドルへの任意のメソッド呼び出し (§2.1)

push は長さを増やすだけなので範囲のエラーを持たない。collect は長さ引数を取らないので array(n, …) のエラーも持たない。

7. 計算量

内部表現は要素の可変 slice。要素数 n に対し:

• get / set / swap / update / length: O(1)
• push: 償却 O(1) (buffer の伸長は倍々で行う)
• array(n, init): O(n) (init で充填)
• from(list): O(n) (コピー)
• frozen: O(1) (buffer を List の格納に move し、ハンドルを封印)
• build(n, init){…}: 充填 O(n) + ブロック本体 + 確定 O(1)
• collect{…}: ブロック本体 (push が償却 O(1)) + 確定 O(1)

ハッシュや永続構造ではなく素の可変 slice を採るのは、Array の目的が「scoped な命令的計算で O(1) 添字更新を得ること」に限られ、確定後は immutable List として広域へ渡るためである。永続的な更新が要る場合は std:map (キー付き・非破壊) を使う。