文字列を段階的に組み立てる - Qiita

プログラムで文字列を組み立てていると、 "(" ^ なにか ^ ")" のように、文字列結合で段階的に結果を組み立てたいことがある。 文字列が小さいことがわかっているうちはこれでもよいのだけれど、文字列が大きくなってくると段々と計算量が気になってくる（特に最適化をしていなければ、文字列の長さを n とすると結合のたびに O(n) のコストがかかる）。 左から右に組み立てることがわかっていれば、OCamlなら Buffer モジュールが使えるが、括弧のようなものがからむとそうも言っていられない。 stringを使うのをやめて、ropeのようなデータ構造を使う手もあるけど、依存ライブラリを増やしたくない場合もある（言語処理系によっては文字列の内部表現がropeになっていて以下のような小細工をする必要がない場合もある）。 ということで、自分でデータ構造をつくってみる。