重複する要素を取り除く in Haskell DouKaku?

与えられたリストxsの中から、 2回以上出現するものを全部取り除いてください。

サンプル入力
[3, 1, 4, 1, 5, 9, 2, 6, 5]
サンプル出力
[3, 4, 9, 2, 6]

これはアレイのuniqの派生問題です。リストとかアレイという言葉は言語によってまちまちの意味で使われているので、「配列のようなもの」という漠然とした意味にとって構いません。

要素がEqクラスのインスタンスなら

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq []
  where uniq xs [] = reverse xs
        uniq xs (y:ys) = case break (y ==) xs of
          (_,[])    -> uniq (y:xs) ys
          (ps,_:qs) -> uniq (ps++qs) ys

{-
uniqOnly [3,1,4,1,5,9,2,6,5]
[3,4,9,2,6]
-}

こっちが正解のはず

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq [] []
  where uniq xs ys [] = reverse xs
        uniq xs ys (z:zs) = case break (z==) xs of
          (_,[]) | z `notElem` ys -> uniq (z:xs) ys zs
                 | otherwise      -> uniq xs ys zs
          (ps,_:qs)               -> uniq (ps++qs) (z:ys) zs

{-
*Main> uniqOnly [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
[4,2,6,8,7]
-}

要素がOrdクラスのインスタンスなら、こちらの方が効率がいいはず

import Data.List

binapp :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
binapp o f x y = f x `o` f y
eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp = binapp (==) 
cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = binapp compare

mapFilter f p xs = [ f x | x <- xs, p x ]

lenOne [x] = True
lenOne _   = False

uniqOnly :: Ord a => [a] -> [a]
uniqOnly = map snd
         . sortBy (cmpapp fst) 
         . mapFilter head lenOne 
         . groupBy (eqapp snd) 
         . sortBy (cmpapp snd) 
         . zip [0..]

foldl を使う版

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = reverse . fst . foldl uniq ([],[])
  where uniq (xs,ys) z = case break (z==) xs of
           (_,[]) | z `notElem` ys -> (z:xs,ys)
                  | otherwise      -> (xs,ys)
           (ps,_:qs)               -> (ps++qs,z:ys)

1	uniqOnly xs = [x \| [x]<-[[z \| z<-xs, z==y] \| y<-xs]]

unfoldr を使ってみた

import Data.List

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = unfoldr phi
  where 
   phi [] = Nothing
   phi (x:xs) = if x `notElem` xs then Just (x,xs)
                else phi (filter (x /=) xs)

Data.Map を使って。

import Data.Map (fromListWith,(!))

uniqOnly xs = filter ((==1).(m!)) xs  where
  m = fromListWith (+) [(x,1)| x <- xs]

DouKaku?

重複する要素を取り除く

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq