列
0個以上の値の集まりを順序を保って保持するデータ構造。 base/Data.List/リスト
n番目の要素にアクセスするにはn個ポインタを辿る必要がある。スタックとして有用。 また、具体的なリストを介在せず、データ構造間の橋渡しとしての役割を果たすことも多い。
他のデータ構造よりもメモリ効率がよく、定数時間で任意の要素にアクセスできるが、要素の追加や更新には線形時間がかかる。ミュータブル版を積極的に活用するアルゴリズムの実装で真価を発揮する。 無印 (Data.Vector): Haskellの値なら何でも格納できる。配列として最低限の機能と性能を備える Unboxed: メモリ上に密に値を並べるため時間・空間効率が良くGCの負担も少ない。数値計算向け 両端の追加・削除が定数時間なためキューとして無難で、結合も対数時間とまずまず。また、任意の場所で切断するのがΟ(log N)なので、それを活かせるなら使い道は広がる。 同じフィンガーツリーの実装だが、切断する「場所」という尺度を自分で定義できるため、さらに切断に特化している。データ構造界の日本刀。代表的な応用として、文字列のためのropeというライブラリがあり、ByteStringの小片を繋げ合わせた構造で、好きな長さに切り取ったり、効率よく結合したりできる。