Clojureの永続ベクターを理解する（2013年・前編）

記事

• Clojureの永続ベクター（persistent vector）を深掘り：ツリー構造に基づく不変データ構造
• 構造的共有（structural sharing）により、コピーなしでO(log n)の更新を実現する仕組みを解説
• シリーズ前編。著者はのちにC言語でRRB-treeを実装

ディスカッション

• 著者がRRB-tree（高速な挿入・削除・マージに対応したvariant）を実装したと紹介するコメントあり
• CHAMP（Steindorferによる改良版HAMT）も発展形として言及
• Scalaにも類似の構造が存在。不変性（immutability）がClojureの並行処理モデルの核心と指摘
• モダンなハードウェアにおけるキャッシュローカリティの観点からの分析を求める声も

HN（Hacker News）で議論を読む

原文（英語）: Understanding Clojure’s Persistent Vectors, pt. 1 (2013)