久しぶりにアルゴリズムが理解できずに詰みかけたので、メモ。
差分リストを用いて、入れ子リストを平坦化(入れ子をなくす)アルゴリズムは
1．nilの平坦化はX#X(空の差分リスト)
2．Xを入れ子のリストとして、X|Xrを平坦化するとY1#Y4。
ただし、Xの平坦化はY1#Y2
Xrの平坦化はY3#Y4
で差分リストを連結するためにY2=Y3となるようにする。
3．Xがリストでないとして、X|Xrを平坦化すると（X|Y1)#Y2になる。ここでXrの平坦化はY1#Y2.
4．Xを入れ子リストとして、X|Xrを平坦化するとY1#Y4になる。
ここで、Xの平坦化はY1#Y2
Xrの平坦化はY2#Y4
となっている。
そこで簡単のため、X|Xr=[[a b] [c d]]とすると
X=[a b]、Xr=[c d]なので、2.(4.)の操作を行い
X → Y1#Y2 (Y1 = [a b c d X]、Y2 = [c d X])
Xr→ Y2#Y4 (Y4 = X)
となる。
これから、Y1#Y4 = [a b c d X]#X となって[a b c d]となり、確かにX|Xrの平坦化された結果となっている。
他の場合もこのように考えると、この繰り返しで平坦化できることが分かる。
