(++) によるリスト連結時の再帰回数を数えてみる（右結合である理由）。

(Real World Haskell—実戦で学ぶ関数型言語プログラミング 13.6 データとしての関数を利用する)
Haskell においてリストを連結するための関数 ++ は下に示すように定義されています。xs ++ ys とした場合はリスト xs の長さに比例して再帰する回数が増加します。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

以下に示したように a ++ b ++ c ++ d と連結すれば再帰するのは 30回ですが、

a = "0123456789"
b = "0123456789"
c = "0123456789"
d = "0123456789"

以下のように連結を繰り返すと、再帰する回数は 60回になってしまいます。

ls1 = a ++ b
ls2 = ls1 ++ c
ls3 = ls2 ++ d

(a++) のように部分適用した関数を作り、 f1 = (a++).(b++) のように関数を合成すれば、 a ++ b ++ c ++ d と書いたときと同じ再帰回数になります。

a1= "0123456789"
b1= "0123456789"
c1= "0123456789"
d1= "0123456789"

f1 :: String -> String
f1 = (a1++).(b1++)

f2 :: String -> String
f2 = f1 .(c1++) 

f3 :: String -> String
f3 = f2 .(d1++)

f3 [] -- => 連結した文字列になる
-- => "0123456789012345678901234567890123456789"

以下が数えるためのソースです。(+#+)で連結する度に再帰した回数を数えて末尾にセットしています。

--  toTLS "0123456789"
-- => [('0',0),('1',0),('2',0),('3',0),('4',0),('5',0),('6',0),('7',0),('8',0),('9',0)]
toTLS :: (Num a1) => [a] -> [(a, a1)]
toTLS [] = []
toTLS (x:xs) = (x,0):toTLS xs

(+#+) :: (Num b) => [(a, b)] -> [(a, b)] -> [(a, b)]
(+#+) xs ys = lsJoin xs ys $ getCnt xs + getCnt ys

lsJoin :: (Num b) => [(a, b)] -> [(a, b)] -> b -> [(a, b)]
lsJoin []     ys n = setToLast ys n
lsJoin (x:xs) ys n = x :lsJoin xs ys (n+1)

-- setToLast [('0',0),('1',0),('2',0),('3',0)] 9999
-- => [('0',0),('1',0),('2',0),('3',9999)]
setToLast :: [(a, b)] -> b -> [(a, b)]
setToLast ls n = reverse $(fst(head rls),n):tail rls
    where
      rls = reverse ls

infixr 5 +#+

getCnt = snd.head.reverse

a=toTLS "0123456789"
b=toTLS "0123456789"
c=toTLS "0123456789"
d=toTLS "0123456789"

-- 一度に連結した場合
cnt1 = getCnt $ a +#+ b +#+ c +#+ d  -- => 30

-- 連結した文字列にさらに加えていく場合
ls1 = a +#+ b      -- getCnt ls1 => 10
                   -- a の長さ：10
ls2 = ls1 +#+ c    -- getCnt ls2 => 30
                   -- ls1 の長さ：20 + ls1を作るコスト:10
ls3 = ls2 +#+ d    -- getCnt ls3 => 60
                   -- ls2 の長さ：30 + ls2を作るコスト:30

-- 部分適用の関数を合成していく場合。
f1 = (a+#+).(b+#+)
f2 = f1 . (c +#+) 
l3 = f2 d

cnt3 = getCnt l3  -- => 30

(++) は右結合ですから、a ++ (b ++ (c ++ d)) と処理されます。
試しに左結合にしてみると、 a +#+ b +#+ c +#+ d の再帰回数は60回になります。

infixl 5 +#+

getCnt $ a +#+ b +#+ c +#+ d  -- => 60

(++) が右結合なのは、 a ++ b ++ c ++ d と書いたとき、演算コストがリスト長の２乗に比例するのを避けるためです。