本文へ移動
Hikari 仕様

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"

n := 5

# 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!  #> 6  (frozen 後は普通の List)

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

1. なぜ List ではなく Array か

Hikari の List・タプル・String は不変で、長さも生成後に変わらない。
要素の差し替え l.[i] = X は静的エラー (immutable-slot-assign) になる
(language-spec.md §7.4)。
要素を変えるには map で新リストを作る。

任意添字への O(1) 散在書き込みを前提にするアルゴリズムでは、map による作り直し (各 O(n)) が O(n²) に膨らむ。
DP テーブル・グリッド更新・in-place sort・Union-Find・counting sort・Fisher–Yates がこの形を取る。

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

plain [...] / List Array (本モジュール)
添字更新 不可 (l.[i] = X はエラー) a.set(i, v) で O(1)
可変性 位置要素は immutable 内部 buffer がメソッドで前進
等価 構造値等価 (§9.1) 参照同一性
確定 — frozen() で immutable List に確定
Sequence / .[i] (§17.5) 持つ 持たない (List に確定してから使う)

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 は持たず、非 Copyable なので std:map / std:set のキーや要素にはできない。
内容を比較したい場合は frozen() で List に確定する。

Array は非 Copyable である (../language-spec.md の複製の節)。内部 buffer が可変で、作り直しても同じものにならないためである。copy の直接の呼び出しは静的エラーになり、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.frozen() の後に a.get 0 と書くと、実行まで進まず use-after-consume になる
(static-analysis.md §2.14)。

封印は追跡が名前を見失う位置のための後詰めである。
確定より前に作った関数リテラルがハンドルを捕獲していると、追跡はその呼びを消費として数えられない。

{|
  a := arr.array(1, 9)
  get0 := {| a.get 0 }  # 所有ハンドルを確定より前に捕獲する
  a.frozen()
  get0!  #> Error — Array.get: use after frozen
}!

arr.build / arr.collect (§3) はブロックを抜けたところで自分で確定する。
ブロックに渡されるのは借用ハンドルなので、そこで h.frozen() を呼ぶと静的エラーになる。
確定は build / collect 自身に任せる。

arr.build(1, 0) { h | h.frozen(); () }  # cannot-consume-borrowed

3. コンストラクター

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

名前 形 効果 意味
array arr.array(n, init) なし 長さ n・全要素 init の Array を作る。n は非負 Int。非 Int は静的エラー、負数は Error
empty arr.empty() なし 長さ 0 の Array を作る。要素は push で足す。要素型は引数から取れないので期待型から取る (§3 末尾)
from arr.from(list) なし 既存 List の内容をコピーした Array を作る (元の List は不変)。非 List は静的エラー
build arr.build(n, init) { h | … } なし(ブロックを透過) array(n, init) でハンドルを作りブロックを実行、終了時に frozen() した immutable List を返す (scoped 糖衣)
collect arr.collect { h | … } なし(ブロックを透過) 長さ未定のハンドルを作りブロックを実行、終了時に frozen() した immutable List を返す。要素は h.push(v) で末尾へ足す

build は「生成・ブロックの実行・確定」をまとめ、ハンドルの凍結し忘れを防ぐ。
次は展開の概念図で、実行するコードではない。

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

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) になる。値の位置で要素型が決まらなければ静的エラーになり、期待型か注釈を要求する。

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。Any を格納する配列は Array(Any) と明示で書く。Array(Int) などの既存のハンドルを Array(Any) として使うことはできない。
  • 要素型は array(n, init) の init・from(list) の要素型から決まる。 empty() と collect は期待型から取る — acc: arr.Array(String) := arr.empty() と束縛注釈を書けば acc.push の引数がその型で検査され、値の位置で要素型が決まらなければ期待型か注釈を要求する静的エラーになる。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「可変コンテナー位置の不変性」)。
  • 実行時の型照合 (matches と静的に証明できないアスクリプション) は、構築時に確定した型引数が厳密に一致することを確かめ、要素も走査する。空の配列でも型引数を区別する。Array(Int) は Array(String) や Array(Any) に一致しない。
    束縛・パラメーター・結果型の注釈では照合しない (../language-spec.md §17)。

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

名前 シグネチャ
array { Int, e | Array(e) }
empty {| Array(e) } (e は期待型から。値の位置で決まらなければ静的エラー)
from { List(e) | Array(e) }
build { Int, e, { Borrowed(Array(e)) | Unit } | List(e) }
collect { { Borrowed(Array(e)) | Unit } | List(e) } (e は期待型から。値の位置で決まらなければ静的エラー)
get { Int | e }
set { Int, e | Borrowed(Array(e)) }
swap { Int, Int | Borrowed(Array(e)) }
update { Int, { e | e } | Borrowed(Array(e)) }
push { e | Borrowed(Array(e)) }
length {| Int }
frozen {| List(e) }

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

set / push / update は受け手を破壊的に書き換えるので、引数の値を e に静的に代入できなければエラーになる (static-analysis.md §2.10「可変なコンテナーへの書き込みの要素型照合」。List の push と同じ契約系の規則)。

arr.array(3, 0).frozen()  #> [0, 0, 0]
(arr.from [10, 20, 30]).frozen()  #> [10, 20, 30]
arr.array(0, 0).frozen()  #> []  (空 Array)
strings := {|
  a: arr.Array(String) := arr.empty()
  a.push "x"
  a.frozen()
}
strings!  #> ["x"]

4. メソッド

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

名前 形 効果 計算量 意味
get a.get(i) なし O(1) 位置 i の要素 (静的型は要素型 e、§3)。非 Int i は静的エラー、範囲外は Error
set a.set(i, v) Mut O(1) 位置 i を v に上書き。a 自身を Borrowed(Array(e)) として返し連鎖可。非 Int i は静的エラー、範囲外は Error
swap a.swap(i, j) Mut O(1) 位置 i と j の要素を交換。a を Borrowed(Array) として返す。範囲外は Error
update a.update(i) { x | x' } Mut(ブロックを透過) O(1) 位置 i を read-modify-write (a.update(k){ c | c+1 })。a を Borrowed(Array) として返す
push a.push(v) Mut 償却 O(1) 末尾に v を足して長さを 1 増やす。a を Borrowed(Array) として返し連鎖可
length a.length() なし O(1) 要素数 (Int)
frozen a.frozen() なし O(1) 内部 buffer を immutable List(e) に確定し、ハンドルを封印 (§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 と同規律)。

# swap で位置を交換する
sorted := arr.build(3, 0) { a |
  a.set(0, 3).set(1, 2).set(2, 1)
  a.swap(0, 2)
}
sorted  #> [1, 2, 3]

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

# 長さが入力次第の組み立て (collect + push)
toks: List(String) := arr.collect { a |
  ["first", "", "second"].each { c |
    when (c != "") {
      a.push c
    }
  }
}
toks  #> ["first", "second"]

5. 多次元

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

# 2 × 3 のグリッドを 1D に潰し、行 1・列 2 に 9 を置く
rows := 2
cols := 3
grid := arr.build(rows * cols, 0) { a |
  a.set(1 * cols + 2, 9)
}
grid  #> [0, 0, 0, 0, 0, 9]
# frozen 後は flat List。2D 形が要れば reshape は呼び側

数値線形代数の Vector/Matrix は不変値型と線形代数演算を扱う別の機能であり、本モジュールには含めない。

6. エラーモデル

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

非 Int 添字・非 Int の n・非 List の from 引数は静的エラー。Error になるもの:

  • get/set/swap/update の範囲外添字
  • array(n, …) の n が負数
  • 封印後 (frozen 済み) のハンドルへの任意のメソッド呼び出し (§2.1)
arr.array(-1, 0)  #> Error (n が負)

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 (キー付き・非破壊) を使う。