動的配列の無難なHaskell実装 - モナドとわたしとコモナド

qiita.com C++、Rust、Pythonなど、他の言語では当たり前のように多用される動的配列だが、Haskell実装は(開発を始めた時点では)見当たらなかったので作ってみたお話*1。 動的配列とはミュータブルな配列の一種で、通常の配列操作だけでなく、末尾への要素の追加・削除が定数時間で行える構造である。確保しておいた領域がいっぱいになったら、その2倍の大きさの領域を確保するという方法によって、漸近的には要素の追加は定数時間となる。 内部の配列には、デファクトスタンダードであるvectorパッケージを用いる。Vectorには無印(boxed)、Unboxed、Storableの三種類の変種があり、それぞれ以下のように使い分ける。 無印(Data.Vector): サンク含め、任意のHaskellのオブジェクトを格納できる。Traversableなどのインスタンスであり、汎用性が高い