本文へ移動
Hikari 仕様

std:parallel — 不変データの並列変換

import { map, filter, fold } := "std:parallel" で取得する。不変データ向けの並列コンビネーターを提供する。並列の実行モデルは language-spec.md §10.1（隔離フローの並列実行）に乗る。

本モジュールは自身では効果を持たない。map / filter / fold は渡した fn の効果を呼び出し元へ透過させる（EffectConduit。../language-spec.md §17.9）。

1. map(list, fn, chunks)

list の各要素を fn で変換した新 List を返す。結果の値と順序は list.map(fn)（prelude List.map）と同一だが、内部で要素群を連続チャンクに分けて並列に評価する。

  • 契約: fn は独立（純粋）であること。要素間の副作用順は未規定。fn が捕獲した可変状態へ書き込むと、その書き込みの位置で Error — 非 Copyable 捕獲（下記）と同じ fail-fast である。捕獲した可変状態は spawn（prelude.md §9.9）と同様にチャンク単位で隔離複製されるので、書き込みを通すと逐次 map と順序ではなく答えそのものが変わる — 踏んだ側が気づけないため、未規定として素通しにはしない。判定の対象は fn の捕獲から到達できる可変な実体で、fn の中で作った値への書き込みは対象にしない。判定は分割の有無に依らず走る — 小さいリストの逐次フォールバック（§4）でも同じ位置で Error になるので、要素数で挙動が変わることはない。
  • 制御構造: fn から return / break / continue を脱出させることは不可（panic）。
  • panic: fn がある要素で panic すると、map 全体がその panic を surface する。並列評価でも最初の失敗要素（最小 index）で決定的に panic する（逐次 map と同じ）。
  • 非 Copyable 捕獲: fn が Future や不透明ハンドルを捕獲していると隔離できないため map 呼び出し自身が panic する（spawn と同じ fail-fast）。
  • 並列度: 既定では実行環境のコア数を上限にチャンク分割する（§4 で明示指定できる）。小さいリストは逐次評価にフォールバックする（結果は同一）。単一スレッド環境（WASM 等）では真の並列にならないが結果は正しい。
import { map } := "std:parallel"

xs := [1, 2, 3, 4, 5, 6, 7, 8]
map(xs, { x | x * x }, 0)   # [1, 4, 9, 16, 25, 36, 49, 64]（xs.map と同一）

2. filter(list, pred, chunks)

list のうち pred が真を返す要素だけを集めた新 List を返す。結果の値と順序は list.filter(pred)（prelude List.filter）と同一だが、内部で要素群を連続チャンクに分けて並列に評価する。

  • 契約: pred は独立（純粋）であること。要素間の副作用順は未規定。
  • pred が Bool 以外を返したら呼び出し位置で Error（prelude の List.filter と同じ扱い — 真偽値以外を truthy 判定に倒さない）。
  • 制御構造・panic・非 Copyable 捕獲・捕獲した可変状態への書き込み・並列度の扱いは §1 の map と同一。
import { filter } := "std:parallel"

filter([1, 2, 3, 4, 5, 6, 7, 8], { x | x % 2 == 0 }, 0)   # [2, 4, 6, 8]

3. fold(list, init, fn, chunks)

list を fn で畳んだ単一の値を返す。内部で連続チャンクに分けて各チャンクを逐次畳み、チャンク結果を昇順に畳む。

  • 契約: fn は結合律を満たすこと — fn(fn(a, b), c) と fn(a, fn(b, c)) が等しいこと。結合律が成り立たない fn の結果は未規定（逐次 fold と一致しない）。
  • 結合律は静的に検査しない。 任意の fn について結合律が成り立つかを決めることはできないので、hikari check の診断は持たない。代わりに hikari lint の non-associative-parallel-fold（../lint.md）が、綴りだけで非結合と分かる形 — fn がちょうど 2 つの未束縛スロットを持ち、本体が - / / / % のいずれかの二項適用ちょうど 1 つで、その左が 1 つ目のスロット・右が 2 つ目のスロットへの裸の参照であるもの（{ a, b | a - b } は当たり、{ a, b | b - a } / { a, b | a - 0 } / { a, b | (a - b) - 1 } は当たらない） — を勧告する。綴りに限るので漏れるが、逐次 fold から機械的に書き換えたときに最も踏まれる形はここで捕まる。漏れた形の結果が未規定であることは上の契約が述べるとおりである。
  • fn は { a, a \| a }・init は要素と同じ型 a である（fold(list: List(a), init: a, fn: { a, a \| a }) -> a）。畳み込みの相手が要素なのかチャンクの結果なのかは分割の仕方で変わるので、要素と結果を別の型にはできない — 上の結合律の契約（fn(fn(a, b), c)）がすでにそれを含意している。別の型の init を書いた形は hikari check が型の食い違いとして断る（以前は型の側だけが許し、チャンクが 2 つ以上に割れた実行で要素をアキュムレーターの位置へ渡して実行時に落ちた）。
  • init は最終畳み込みの起点として一度だけ使う。チャンクごとの種にはしない（そうすると結合律だけでは足りず単位元性まで要求することになる）。
  • 空リストは init をそのまま返す。
  • 制御構造・panic・非 Copyable 捕獲・捕獲した可変状態への書き込み・並列度の扱いは §1 の map と同一。
import { fold } := "std:parallel"

fold([1, 2, 3, 4], 0, { a, b | a + b }, 0)   # 10（+ は結合律を満たす）

4. 並列度の設定

map / filter / fold は末尾に chunks（チャンク数、Int）を取る。省略できない（index.md）— 自動に任せるなら 0 を書く。

  • 0 は自動（実行環境のコア数を上限に分割する）を意味する。
  • chunks が要素数を超えるときは要素数に丸める。
  • 丸めた結果が 1 以下になるときは逐次評価にフォールバックする（結果は同一）。
  • 負数または非 Int の chunks は呼び出し位置で Error。
import { map } := "std:parallel"

map([1, 2, 3, 4, 5, 6, 7, 8], { x | x * x }, 2)   # 2 チャンクに分けて評価

5. 多重度型の扱い

並列コンビネーターは fn を要素ごとに起動するので、外側の多重度型の値の消費は静的に禁じられる（static-analysis.md §2.14 の consume-in-unknown-arity-block）。借用（Borrowed）として参照するだけなら自由だが、借用の値をここへ捕獲することはできない（language-spec.md §17.8「借用は保存できない」の別フローへの捕獲の行）。多重度型の値を並列に扱いたい場合は、要素ごとに分割してから各要素を所有として渡す形にする。