std::uniqueと似たような関数 List.nub

unique欲しいなーでもないなーと思ってたらやっぱりあった。ただ、内部実装がO(N^2)、つまりソート済みでないリストも受け入れてしまう実装になっている模様。O(NlogN)ソート+O(N)でやった方が速いので、必要に応じた使い分けが重要っぽい。

つーか近々Haskell標準ライブラリの旅をしてみよう…。なんか良いリファレンスあると良いな。

unique [] = []
unique (x:xs) = x : unique' x xs
  where
    unique' _ [] = []
    unique' prev (x:xs)
      | x == prev = unique' prev xs
      | otherwise = x : unique' x xs

とりあえず副産物。渡すリストはソート済みと仮定。最後にreverseで末尾再帰可なパターン。どっちが速いのかわからんけども。