「Haskellのリストを左結合で連結すると効率が悪い」というのは色んなところで言われているし有名だけど、その理由を詳しく解説している日本語の記事がググっても見あたらなかったので書いてみます。
「左結合で連結する」というのはつまり (a ++ b) ++ c ってことです。
右結合・左結合については Haskellの右結合と左結合 などを参照してください。
解説
まずはリストの連結関数 (++) の定義をおさらいします。
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
左のリストが空でない間はずっと下のパターンを通るので、
[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]
上記のように展開されていきます。
つまりこの関数は、
- 左のリストを
a:b:c: ... :[]の形に展開していく - 最後の
[]を右のリストに置き換える
という手順を踏んでいることに注目してください。
効率の悪い (a ++ b) ++ c をこの手順に則って見ていくと、
- 括弧がついてるので、 a ++ b を先に評価する
- a を展開する
- a の末尾の [] が b になり、新しいリスト ab ができる
- ab ++ c を評価する
- ab を展開する (a にあった要素も、もう一度展開される)
- ab の末尾の [] が c になり、新しいリスト abc ができる
となって、同じ要素を重複して走査してしまっています。
一方、効率の良い a ++ (b ++ c) を同じ手順に則って見ていくと、
- 括弧がついてるので b ++ c を先に評価する
- b を展開する
- b の末尾の [] が c になり、新しいリスト bc ができる
- a ++ bc を評価する
- a を展開する
- a の末尾の [] が bc になり、新しいリスト abc ができる
となって、今度は同じ要素が重複して走査されることはありません。
検証
実際にどう評価されるかを確かめるためには Debug.Trace が使えます。
以下は検証用のコードです。
Lib.hs
{-# LANGUAGE Strict, StrictData #-}
-- 遅延評価の場合は出力順が変わってややこしくなるので、正格評価にする
-- 結合の効率はどちらも変わらない
module Lib where
import Debug.Trace
-- 正格評価なリストを作る
-- StrictモードのHaskellでも、標準のリスト([a])は遅延評価のままなので、このモジュール内でデータ構造を定義する必要がある
-- このListは正格評価される
data List a = Nil | Cons a (List a) deriving (Show)
toL :: [a] -> List a
toL [] = Nil
toL (x:xs) = x `Cons` toL xs
infixr 5 +#+
(+#+) Nil ys = ys
(+#+) (x `Cons` xs) ys = (traceShowId x) `Cons` (xs +#+ ys) -- traceShowId で評価された時に値を表示する
-- List a を評価するためだけの関数
-- seq は浅いので、深く評価するために専用のものを作る
eval :: List a -> ()
eval Nil = ()
eval (x `Cons` xs) = x `seq` eval xs
GHCi で確かめてみましょう。
左結合の場合
ghci> a = toL [1..5]
ghci> b = toL [6..10]
ghci> c = toL [11..15]
ghci> eval $ (a +#+ b) +#+ c
1 # a を展開
2
3
4
5 # a の展開完了。 ab ができる
1 # ab を展開
2
3
4
5
6
7
8
9
10 # ab を展開完了。 abc ができる
()
右結合の場合
ghci> a = toL [1..5]
ghci> b = toL [6..10]
ghci> c = toL [11..15]
ghci> eval $ a +#+ (b +#+ c)
6 # b を展開
7
8
9
10 # b の展開完了。 bc ができる
1 # a を展開
2
3
4
5 # a の展開完了。 abc ができる
()
以上です。
分かりやすくなってると良いなぁ。