top page > computer > haskell > web_lecture > for_programmer > diff_list.html
更新日:
文責: 重城良国

アルゴリズム: 差分リスト

(工事中 60%)

リストの結合

リストの結合について考えよう。

(x : xs) ++ ys = x : (xs ++ ys)
_ ++ ys = ys

[1, 2, 3] ++ [4, 5]を展開してみよう。

[1, 2, 3] ++ [4, 5]
1 : ([2, 3] ++ [4, 5])
1 : 2 : ([3] ++ [4, 5])
1 : 2 : 3 : ([] ++ [4, 5])
1 : 2 : 3 : [4, 5]

リスト[4, 5]の先頭に3, 2, 1を順に足していくという操作が行われる。

実行効率

Haskellの評価方法からすると厳密な言いかたではないが、リストの結合は前のリストの長さに比例した時間がかかる。このとき以下の2つの操作を考えてみよう。

[1, 2, 3] ++ ([4, 5, 6, 7] ++ [8, 9])

([1, 2, 3] ++ [4, 5, 6, 7]) ++ [8, 9]

リストの結合を連鎖させているが、前者は右結合であり、後者は左結合となっている。それぞれにかかる時間を考えると右結合のほうでは3 + 4で7となるのに対して、後者では3 + 7で10となる。

右結合のほうは[8, 9]に7, 6, 5, 4を追加したうえで3, 2, 1を追加している。左結合のほうは[4, 5, 6, 7]に3, 2, 1を追加したうえで、[8, 9]に7, 6, 5, 4, 3, 2, 1を追加している。

右結合のほうが左結合よりも効率的

左結合でリストの結合を連鎖させていくと前側のリストがどんどん大きくなってしまい、効率が低下していく。右結合でのリストの結合の連鎖では前側のリストの大きさは与えられるリストのサイズのままだ。効率は一定の水準に保たれる。

右結合を強制する

どのような順に結合しても結果としての結合の順が右結合になるようなデータ構造を考えることができる。リスト[1, 2, 3]を直接扱うかわりに「[1, 2, 3]を先頭に追加する」関数を考える。すると[1, 2, 3]と[4, 5, 6]を結合することは、「[1, 2, 3]を先頭に追加する」関数と「[4, 5, 6]を先頭に追加する」関数との関数結合となる。

[1, 2, 3] ++ [4, 5, 6]

([1, 2, 3] ++) . ([4, 5, 6] ++)

「先頭にリストを追加する関数」はどのような順で関数結合したとしても結果として行われる「リストの結合」は右結合となる。関数からリストをとりだすには空リストを与えてやればいい。

([1, 2, 3] ++) . ([4, 5, 6] ++) $ []

まとめ

リストを結合するとき、リストそのものではなく、「先頭にリストを追加する関数」を考えてやることで、リストの結合の連鎖に右結合を強制することができる。

「構文: infix」へもどる 「型クラス: Show」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics