Haskellの差分リストは一般に([1,2,3] ++) . ([4,5,6] ++)のようにセクションで示される。しかしこれは連結の際に左側のリストの要素をたどって末尾を見るので計算量がリストの長さに比例して増加しO(n)となる。一方CTMCP(コンピュータプログラミングの概念・技法・モデル)では要素をたどらず直接末尾を見るので計算量がリストの長さに比例して増加せずO(1)となる実装がOzにより示され、そしてこの効率性が差分リストの特徴とされている。Haskellも遅延評価の場合は連結コストが使用時のコストに同化されO(1)となるかもしれないが正格評価の場合は連結時に直ちにO(n)のコストを支払わなければならず、さらにこの状況は完全な正格評価でなくともデータが正格あるいは評価済みであるだけでも生じるため遅延評価の中でも無縁な話ではない。これは本当に差分リストとして説明してよいのだろうか？どうも過日のなんちゃってクイックソートと同じ種類の誤りを含んでいるように見える。
そういえばHaskellの差分リストについて気になることがあったのを思い出したのでアドカレのネタに書いてみた。
議論の結果、Haskellの差分リストがO(n)で非効率となる状況は連結演算まで正格となる状況まで限定できそうであるという結論になった。つまり差分リストの問題点は指摘のとおりだが正格性依存な分クイックソートよりはマシ。
