重複の削除

Haskell 30分プログラム

30分プログラム、その131。重複する要素の削除。

重複した要素が、すべて削除されるところがnubと違う。

> nub [1,1]
*Main> nub [1,1]
[1]

*Main> uniq [1,1]
[]

使い方

普通につくったuniqと、ちょっと工夫したuniq2がある。
たぶん、uniqはO(N*N)で、uniq2は(N)。ちゃんと計算したわけじゃないけど。

*Main> :set +s
*Main> let xs = [1..1000] ++ [1..1000]

*Main> uniq (xs++xs)
[]
(0.53 secs, 16557356 bytes)

*Main> uniq2 (xs++xs)
[]
(0.21 secs, 3464192 bytes)

よし、ちゃんと効率がよくなってる。

ソースコード

import Data.List
uniq :: (Eq a) =>[a] -> [a]
uniq (x:xs) = if x `elem` xs then
                  delete x $ uniq xs
              else
                  x:uniq xs
uniq [] = []

delTopBy f x l@(y:ys) 
    | f x y    = delTopBy f x ys
    | otherwise = l
delTopBy _ _ [] = []

nodupBy :: (Eq a) => (a->a->Bool)->[a] -> [a]
nodupBy f (x:l@(y:xs)) = if f x y then
                             nodupBy f $ delTopBy f x xs
                         else
                             x:(nodupBy f l)
nodupBy _ x = x

uniq2 xs = map fst $ 
           sortBy (compose compare snd) $
           nodupBy (compose (==) fst) $
           sortBy (compose compare fst) $
           zip xs [0..]
    where
      compose f g a b = f (g a) (g b) -- これ標準でありそう

参考