すごいハスケルよりWriter Monadで混乱した、リストの左右結合の差について

Learn You a Haskell for Great Goodより。

List の結合が連続するとき、どちらから結合させるように設計するべきかで少々混乱した、以下自分用のメモ。

(++) 関数

concatenation (++)は中置演算子として使われることも多くって、その際の左側のリスト つまり最初のリストを走った後、その後ろにふたつ目のリストをつなげるという作業を行う、らしい。
リストの説明でよく見る図、Lispでもよく見た気がする
つまりひとつ目のリストの終端記号を見つけるまで走って、終端記号をふたつ目のリストの頭を指すポインタに置き換えてる、という理解だろうか。

したがってChapter 1 page 8 でも述べているが連続して使う場合は左から新しいリストを作用させていったほうが得である、とのこと。
つまり左から新しいリストを作用させていけば、すでにつなげてあるリストを走る必要はない、逆に右につけていくとすでにつなげたリストを再度走っていく必要があるので大変無駄である、と。

Be careful when repeatedly using the ++ operator on long strings. When you put together two lists, Haskell has to walk through the entire first list (the one on the left side of ++). That’s not a problem when dealing with smaller lists, but appending something to the end of a list with fifty million entries is going to take a while.

gcd' 関数

さてここからが問題。

gcd'.hs

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
  | b == 0 = do
      tell ["Finished with " ++ show a]
      return a
  | otherwise = do
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
       gcd' b (a `mod` b)

これは良い実装とされてて、実行結果は次のような感じに。
ちなみにdo 記法は逐次実行の再発明らしい、つまり手続き型と思ったら良い、とのこと。

> mapM_ putStrLn $ snd $ runWriter $ gcd' 8 3
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1

do 記法が苦手な人は(>>)をthenに読み替えて

gcd''.hs

gcd'' :: Int -> Int -> Writer [String] Int
gcd'' a b
  | b == 0 = tell ["Finished with " ++ show a]
             >> (return a)
  | otherwise = tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
                >> (gcd'' b (a `mod` b))

としても、多分読みにくいと思います、、、（do 記法も嫌いでかつこれも読みにくいとなるとどうしたら良いのか、、、ま、またこれは別の問題ですが、あるいは慣れの問題でしょう。）

説明の前に悪い例の実装をば。

gcdReverse.hs

gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
  | b == 0 = do
      tell["Finished with " ++ show a]
      return a
  | otherwise = do
      result <- gcdReverse b (a `mod` b)
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
      return result

これは結果を逆順に返します。

> runWriter $ gcdReverse 8 3
(1,["Finished with 1","2 mod 1 = 0","3 mod 2 = 1","8 mod 3 = 2"])

Writer Monadの実装

さて、こいつらを料理するためにはWriter Monadがどう実装されているかが必要で、以下の様な感じ。

instance (Monoid w) => Monad (Writer w) where
    return x = Writer (x, mempty)
    (Writer (x, v)) >>= f = let (Writer (y, v')) = f x
                            in Writer (y, v `mappend` v')

モノイドのインスタンスとしてリストに限定して考えればタプルの2つめの要素は(++)でつながっていくということである、したがって結合だけ考えればWriter Monadのインスタンスもリストだと大雑把に言っていいと思う。
（まぁ圏論的に言えば自己関手の圏のモノイド対象がモナドなわけで、その積は（弱められていなければ）モノイドと一緒なのでつまるところのところ一緒だという話）

良し悪し

逆順に吐き出すgcdReverseが効率が悪そうな実装である、というのはなんとなく直観的に感じるので解析してみよう、つまりはリストと見た時に何度も同じ要素の上を走ってしまっているのだということを示したいわけだ。
どちらの実装もtell が吐き出したリストをどう結合するかというところが違うのだろうとあたりをつけてみる、さてgcdReverse については

It does the recursion first and binds its resulting value to result. Then it adds the current step to the log, but the current step goes at the end of the log that was produced by the recursion. At the end, it presents the result of the recursion as the final result.

とおっしゃってる、それから察するにgcd'はtellが吐いたリストを

c++(b++a)

と結合していて、逆にgcdReverseは

(c++b)++a

と結合しているのだろうと踏んだ、あとは確認してみるだけである。

確認

gcd'.hs

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
  | b == 0 = do
      tell ["Finished with " ++ show a]
      return a
  | otherwise = do
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
       gcd' b (a `mod` b)

なのでtell で作られた文字列リストはWriter [String] のmappendによって

["8 mod 3 = 2"] ++ (["3 mod 2 = 1"] ++ (["2 mod 1 = 0"] ++ ["Finished with 1"]))

と繋がると、まぁそうでしょうよ、では次。

gcdReverse.hs

gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
  | b == 0 = do
      tell["Finished with " ++ show a]
      return a
  | otherwise = do
      result <- gcdReverse b (a `mod` b)
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
      return result

今度は

This function is inefficient because it ends up associating the use of ++ to the left instead of to the right.

とおっしゃてるのでさて見てみよう。

まずはb==0 にヒットしないのでresult に自己再起呼び出しが束縛される。
そののちtell が文字列を吐いて、最後にreturn でresult の中身がWriter Monadの値にラップされる、と。

あるいはdesugar したgcdReverse' をみるともっとはっきり分かるかもしれない：

gcdReverse'.hs

gcdReverse' :: Int -> Int -> Writer [String] Int
gcdReverse' a b
  | b == 0 = tell["Finished with " ++ show a]
             >> return a
  | otherwise = gcdReverse b (a `mod` b)
                >>= (\result -> tell [show a ++ " mod " ++ show b ++ " = " ++ show (    a `mod` b)]
                >> return result)

したがって

[recursion] ++ "8 mod 3 = 2" 

という風に再帰的に自分を呼び出している、すなわち

(("Finished with 1" ++ "2 mod 1 = 0") ++ "3 mod 2 = 1") ++ "8 mod 3 = 2"

おぉ、なるほど、こりゃ確かに毎度毎度同じリストの上を走って末端を探す作業をしているから効率悪いわけだわ。

結論

This function is inefficient because it ends up associating the use of ++ to the left instead of to the right.

とシンプルにおっしゃっていることが最初さっぱりわからなかったがこうやってアルゴリズムにそって簡単な例を追っかけてみたらよくわかりました。

追記（差分リスト）

その直後page 307 で新しいデータ構造を導入してパフォーマンスの改善を図っている。

DiffList.hs

newtype DiffList a = DiffList { getDiffList :: [a] -> [a]}

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs ++)
fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

この差分リストを用いるとリストの結合はただの関数の積になる

f `append` g = \xs -> f (g xs)

あるいはより具体的に"dog" と "meat"が

("dog" ++) `append` ("meat" ++) = \xs -> "dog" ++ ("meat" ++ xs)

となり、リストの結合が逐次改善されるらしい、見てみる。
まずは困ったちゃんを用意：

("cat" ++ "fish") ++ "burger"

これがtoDiffListによって差分リストに化けてる、つまり

(\xs -> "cat" + xs) `append` (\ys -> "fish" ++ ys)
= \xs -> "cat" ++ ("fish" ++ xs)

したがって全体では

(\xs -> "cat" ++ ("fish" ++ xs)) `append` (\zs -> "burger" ++ zs)
=\xs -> "cat" ++ ("fish" ++ ("burger" ++ xs)

となる、すなわち

(a ++ b) ++ c => a' ++ (b' ++ c')

となったということである、したがってリストの結合の際のパフォーマンスが上がるというわけだ。