差分リスト(Difference List)について

Difference Listとは？

その名の通り、差分(difference)リストです。差分リストはListのappendのパフォーマンスが結合に依存する問題を解消します。

Listのappendは結合順によって計算量が異なる

appendは結合順を変えても意味としては同じです。しかし、cons listではappendの結合順によりパフォーマンスがかなり異なります。

たとえば以下のコードのlist1とlist2では、圧倒的にlist2のほうが早いです。

list1 = foldl (++) [] $ replicate 10000 $ replicate 10 0
list2 = foldr (++) [] $ replicate 10000 $ replicate 10 0

main = do
  print $ take 1000 list1 -- 遅い
  print $ take 1000 list2 -- 早い

これは両者の結合順が異なることに由来しています。

• list1は左結合(([0,0,0] ++ [0,0,0]) ++ [0,0,0]) ++ [0,0,0]
• list2は右結合[0,0,0] ++ ([0,0,0] ++ ([0,0,0] ++ [0,0,0]))

Cons listはappendする際に左のリストの中身をひとつずつ右へ移します。そのため、左辺を伸ばす結合をしているlist1はかなり遅くなります。

計算量を見てみます。list1はappendするたびに左辺の長さが10ずつ増え、10000回結合しています。そのため、計算量は5*(10000)*(10000+1)になっています。結合回数をNとするとO(N²)かかります。

対して、list2は左辺のリストの長さは固定で10です。そのため、10000回結合しても10*(10000)しかかかりません。結合回数をNとすればO(N)しかかかりません。

このように appendするときは原則右結合で書く必要があります。しかし、appendしたいだけなのに結合を気にするのはひどく辛いです。また、左結合が避けられないケースもあります。

このappendの結合性の問題を解消したのが差分リストです。

差分リストは右結合を左結合へ変換する

差分リストは関数合成を用いることで結合を変換します。よくわからないと思うので、コードを見てください。

list3 = ((([0] ++ [0]) ++ [0]) ++ [0]) ++ [0]
diff_list = (((([0] ++) . ([0] ++)) . ([0] ++)) . ([0] ++)) . ([0] ++) $ []

こんな感じに、「[0] ++」という関数を合成していくことでappendを表現しています。この関数に[]を適用すると通常のリストへ変換できます。

見やすさのために補助関数や型を導入します。

type DiffList a = [a] -> [a]

-- abs: 受け取ったDiffListをListへ変換する
abs :: DiffList a -> [a]
abs l = l []

-- rep: 受け取ったListをDiffListへ変換する
rep :: [a] -> DiffList a
rep = (++)

-- ++の代わりに+++を用いて結合する
(+++) :: DiffList a -> DiffList a -> DiffList a
(+++) = (.)

これで結合性が解消できます。テストしてみます。

main = do
  print $ take 10000 $ Main.abs $ foldl (+++) (rep []) $ replicate 10000 $ rep $ replicate 10 0
  print $ take 10000 $ Main.abs $ foldr (+++) (rep []) $ replicate 10000 $ rep $ replicate 10 0

どちらもかなり高速で動作します！

差分リストのデメリット

ただ、差分リストにもデメリットはあります。それが変換をしなければならないという点です。例として、差分リストを用いてキューを実装することを考えます。

頻繁な変更に向かない

type DiffList a = [a] -> [a]
type Queue a = DiffList a

abs :: DiffList a -> [a]
abs l = l []

rep :: [a] -> DiffList a
rep = (++)

(+++) :: DiffList a -> DiffList a -> DiffList a
(+++) = (.)

push x l = l +++ rep [x]
pop = rep . tail . Main.abs

main = do
    print $ Main.abs (pop $ pop $ push 3 $ push 2 $ push 1 (rep []))

popを見るとわかりますが、1回popするたびにrepとabsが呼ばれてDiffList -> List -> DiffListという変換が行われています。この変換のうち、DiffList -> Listの部分が差分リストの長さぶんだけコストがかかってしまいます(diff_list ++ []を実行しているため)。1回popするたびに長さぶんコストがかかってしまうのはつらいので、差分リストをリストへ変換したくなりますよね？しかし、一度リストへ変換してしまうと、今度はpushができなくなります。そのため、pushしたくなったらまた差分リストへ変換する必要があります。

(まあそもそもqueueの実装に使わなければ良いだけの話ですが)

まとめると、pushしたあとにpopと、差分リストの長さだけコストがかかってしまいます。しかし、キューを使いたいとき、pushする箇所とpopする箇所がまとまっていることのほうが少ないです。困りましたね…

差分リストはheadに多大なコストがかかる

他にもあります。それが、差分リストはheadするのが容易でないという点です。差分リストの実態はただの関数です。そのため、差分リストの先頭を見るには、一度リストへ変換する必要があります。この変換には差分リストの長さ分コストがかかります。通常のリストへのheadが定数時間でできることを考えるとかなり大きなデメリットです。

さらに言うと、「差分リストが空かどうか」の判定でさえ一度普通のリストへ変換しなければできません。驚きですね。

Type Aligned Sequenceなら解決できる

と、そこで登場するのがType Aligned Sequenceです。詳しくは論文を読んでください。