12

29

[Haskell] ある文字列が、すべてユニークであるかどうかを判定するアルゴリズム

2012.12.29(18:16)

世界で闘うプログラミング力を鍛える150問
http://www.amazon.co.jp/dp/4839942390/
の問題1.1をHaskellで解いてみた

ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズムを実装してください。また、それを実装するのに新たなデータ構造が使えない場合、どのようにすればよいですか?

{-# OPTIONS -Wall -Werror #-}

-- | ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズム

module IsUniqueChars where
import Test.HUnit
import Test.QuickCheck

-- | ------------------- アルゴリズム1 ----------------------
-- | 先頭の文字が2文字目以降のどこにも表れなければTrue
isUniqueHead :: String->Bool
isUniqueHead []     = True
isUniqueHead (_:[]) = True
isUniqueHead (x:xs) = and $ map (/=x) xs

-- | 先頭の文字が2文字目以降のどこにも表れないことを、先頭の文字から順に繰り返す
isUniqueChars2 :: String->Bool
isUniqueChars2 []           = True
isUniqueChars2 (_:[])       = True
isUniqueChars2 whole@(_:xs) = (isUniqueHead whole) && (isUniqueChars2 xs)

-- | ある文字列が、すべてユニークである(重複する文字がない)ときTrue
isUniqueChars :: String->Bool
isUniqueChars s = if length s > 256 then False
                                    else isUniqueChars2 s

-- | ------------------- アルゴリズム2 ----------------------
-- | クイックソート
qsort :: (Ord a) => [a] -> [a]  
qsort []     = []  
qsort (x:xs) = qsort left ++ [x] ++ qsort right
               where left  = filter (< x)  xs  
                     right = filter (>= x) xs  

-- | ソートした文字列を先頭から隣り合う2文字ずつ比較し、すべて違っているときにTrue
isUniqueChars2' :: String->Bool
isUniqueChars2' s = and [ m /= n | (m,n) <- zip sorted (tail sorted)]
                    where sorted = qsort s

-- | ある文字列が、すべてユニークである(重複する文字がない)ときTrue
isUniqueChars' :: String->Bool
isUniqueChars' s = if length s > 256 then False
                                     else isUniqueChars2' s

-- | ------------------- HUnitテストとquickCheck ----------------------
isUniqueCharsTest :: (String->Bool)->Test
isUniqueCharsTest func = test [
      func "" ~=? True,
      func "a" ~=? True,
      func "ab" ~=? True,

      func "aa" ~=? False,
      func "aba" ~=? False,
      func "abab" ~=? False,
      func "abba" ~=? False,

      func "abcde" ~=? True,
      func "abcda" ~=? False,
      func "abcdb" ~=? False,
      func "abcdc" ~=? False,
      func "abcdd" ~=? False,
      func ['\x00'..'\xff']  ~=? True,
      func ['\x00'..'\x100']  ~=? False,
              True ~=? True
    ]

testIsUniqueCharss :: [(String->Bool)] -> IO ()
testIsUniqueCharss [] = return ()
testIsUniqueCharss (x:xs) = do
   _ <- runTestTT $ isUniqueCharsTest x
   testIsUniqueCharss xs

-- | quickCheck
prop_isUniqueChars :: String->Bool
prop_isUniqueChars s = isUniqueChars s == isUniqueChars' s

main :: IO ()
main = do
  testIsUniqueCharss [isUniqueChars, isUniqueChars']
  quickCheck prop_isUniqueChars
  return ()





↑最後の行はゴミm(_ _)m
プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示