数字混じり文字列ソート

練習に「数字混じり文字列ソート」をしてみました。

例1:
辞書順ソート: 1.txt, 10.txt, 100.txt, 2.txt, 20.txt
数字混じり文字列ソート: 1.txt, 2.txt, 10.txt, 20.txt, 100.txt

例2:
辞書順ソート: x12, x13, x1A, x1B, xAB
数字混じり文字列ソート: x1A, x1B, x12, x13, xAB

例3:
辞書順ソート: A10B1, A10B10, A10B2, A1B1, A1B10, A1B2, A2B1, A2B10, A2B2
数字混じり文字列ソート: A1B1, A1B2, A1B10, A2B1, A2B2, A2B10, A10B1, A10B2, A10B10

• 二つの文字列を比較する関数を定義、それを使って sortBy します。

import Data.Char
import Data.List

cmp :: String -> String -> Ordering
cmp [] [] = EQ
cmp a@(x:xs) b@(y:ys) =
    if (isDigit x) && (isDigit y)
        then if aNumber == bNumber
                  then cmp aStr bStr
                  else compare aNumber bNumber
        else if x == y then cmp xs ys else compare x y
    where
      (aDigit, aStr) = span isDigit a
      (bDigit, bStr) = span isDigit b
      aNumber = (read aDigit):: Integer
      bNumber = (read bDigit):: Integer

numStringSort :: [String] -> [String]
numStringSort = sortBy cmp

> numStringSort ["1.txt", "10.txt", "100.txt", "2.txt", "20.txt"]
-- > ["1.txt","2.txt","10.txt","20.txt","100.txt"]
> numStringSort ["x12", "x13", "x1A", "x1B", "xAB"]
-- > ["x1A","x1B","x12","x13","xAB"]
> numStringSort ["A10B1", "A10B10", "A10B2", "A1B1", "A1B10", "A1B2", "A2B1", "A2B10", "A2B2"]
-- > ["A1B1","A1B2","A1B10","A2B1","A2B2","A2B10","A10B1","A10B2","A10B10"]

• Ruby と同じように "A10B10" なら [S "A",I 10,S "B",I 10] というリストを作って比較する戦略。

import Data.Char
import Data.List

data Mix = S String | I Integer deriving (Eq,Ord,Show)


toMixList :: String -> [Mix]
toMixList [] = []
toMixList inStr@(x:xs) = 
   if (isDigit x)
     then (I (read digit)): toMixList str
     else (S str2)        : toMixList digit2
    where
      (digit, str)    = span isDigit inStr
      (str2 , digit2) = span (not.isDigit) inStr

numStringSort :: [String] -> [String]
numStringSort = map snd . sort . map (\x ->(toMixList x,x))

• 正規表現を使って。

import Text.Regex.Posix
import Data.List

data Mix = S String | I Integer deriving (Eq,Ord,Show)

toMixList :: String -> [Mix]
toMixList [] = []
toMixList str = case (headStr,match) of
                  (a@(x:xs),b@(y:ys)) -> (S a): toInteger b :toMixList tailStr
                  (a@(x:xs),[])       -> (S a): toMixList tailStr
                  ([],b@(y:ys))       -> toInteger b :toMixList tailStr
    where
        toInteger x = (I (read x))
        (headStr,match,tailStr) =  str =~ "[0-9]+" ::(String,String,String)

numStringSort :: [String] -> [String]
numStringSort = map snd . sort . map (\x ->(toMixList x,x))

• Parsec を使って。

import Text.ParserCombinators.Parsec
import Data.List

data Mix = S String | I Integer deriving (Eq,Ord,Show)

number :: Parser Mix
number  = many1 digit >>= \num -> return $ I(read num)

alphabet :: Parser Mix
alphabet = many1 letter >>= \str -> return (S str)

parseText :: Parser [Mix]
parseText = many ( alphabet <|> number) >>= return

readText :: String -> [Mix]
readText input = case parse parseText "sort" input of
    Left  err -> error $ show err
    Right val -> val

numStringSort :: [String] -> [String]
numStringSort = map snd . sort . map (\x ->(readText x,x))