ふつうのHaskell勉強日誌
ふつうのHaskellプログラミング 初版 p246
練習問題 9.6
問題: 新しい型"Line"を定義し、sortLines関数でソートする
Line型は`data Lines = Lines {number::Int, string::String} deriving Show`で定義されるように、行番号とテキストで構成されます。
問題では、Data.Linesで定義されているsortByを使用することを推奨していますが、そうやって書いてもつまらないのでsortBy'を定義して問いてみました。
といっても、引数を関数を取るqsort関数を定義するだけですね。
module Main where main = do print $ sortLines mylines data Line = Line {number::Int, string::String} deriving Show mylines :: [Line] mylines = [Line 7 "piyo", Line 5 "hogehoge", Line 4 "fugafuga", Line 3 "piyo", Line 2 "fuga", Line 1 "hoge", Line 6 "piyopiyo"] sortLines :: [Line] -> [Line] sortLines = sortBy' (\(Line n _) (Line m _) -> compare n m) where sortBy' :: (a -> a -> Ordering) -> [a] -> [a] sortBy' _ [] = [] sortBy' f (piv:xs) = sortBy' f (filter (\x -> f x piv == LT || f x piv == EQ ) xs) ++ [piv] ++ sortBy' f (filter (\x -> f x piv == GT) xs) 出力: [Line {number = 1, string = "hoge"},Line {number = 2, string = "fuga"},Line {number = 3, string = "piyo"},Line {number = 4, string = "fugafuga"},Line {number = 5, string = "hogehoge"},Line {number = 6, string = "piyopiyo"},Line {number = 7, string = "piyo"}]
また、これも出題にはありませんでしたが、LineをOrd型クラスのインスタンスとすればもっとスマートではないかと思って下記の実装もしてみました。
module Main where main = do print $ qsort' mylines data Line = Line {number::Int, string::String} deriving (Show, Eq) instance Ord Line where compare (Line x _) (Line x' _) = compare x x' mylines :: [Line] mylines = [Line 7 "piyo", Line 5 "hogehoge", Line 4 "fugafuga", Line 3 "piyo", Line 2 "fuga", Line 1 "hoge", Line 6 "piyopiyo"] qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (piv:xs) = qsort' (filter (<= piv) xs) ++ [piv] ++ qsort' (filter (> piv) xs)
なお、この実装２つのの問題点として、「おなじnumberを持つLineが複数あった場合、それらのソート順序は考慮されない」というものが挙げられます。
通常、同一の行番号を持つLineが複数存在するということは考えられませんが
・同一の行番号を持つLineを排除する機構は作れるのか
・同一の行番号を持つLineのリストを許容した場合、「まず行番号でソートし、同一の行番号をもつ行同士は文字列でソートする」という実装はどう行なうか
が課題といえます。
