unwordsのコスト

Haskellで遊ぶよ さんのunwordsはO(n^2)?を読んで、unwordsのコスト、僕も考えてみました。コストはひょっとしたらO(n)なような気がしています。なぜかというと、unwordsがfoldrを使っているからかもと…間違ってるかもしれませんが…

foldrはright associativeなので、

foldr1 (++) ["a", "b", "c", "d"] = "a" ++ ("b" ++ ("c" ++ "d"))

ということになって、さらに++もright associativeで

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

なので、それぞれの文字列は１回ずつしかスキャンされていないような気がします…さらに遅延評価なのでリストの結合も使われる部分だけしか行われないですね…

これがfoldl1なんて使っていたら確かにO(n^2)になりそうですね…Associativityが右か左かでコストが変わってしまうのが面白いですね。今まであんまり理解しようとしていなかったのでよい勉強になりました。

時間を見つけて実際に実行時間を計測してみたらもっとはっきりしますね…