読者です 読者をやめる 読者になる 読者になる

定食屋おろポン

おろしポン酢と青ネギはかけ放題です

ふつうの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)

なお、この実装2つのの問題点として、「おなじnumberを持つLineが複数あった場合、それらのソート順序は考慮されない」というものが挙げられます。
通常、同一の行番号を持つLineが複数存在するということは考えられませんが
・同一の行番号を持つLineを排除する機構は作れるのか
・同一の行番号を持つLineのリストを許容した場合、「まず行番号でソートし、同一の行番号をもつ行同士は文字列でソートする」という実装はどう行なうか
が課題といえます。

「同一の行番号を持つLineを排除する機構は作れるのか」に関して

手続き型言語脳としては、「インスタンス変数としてLineの配列を保持する新しいクラスを定義し、addLine(line)インスタンスメソッドで重複チェックを行なう。重複していればExceptionを投げる」といった方法が考えられます。
Haskellでは
・行の追加関数を用意し、その関数以外では行を追加できないようにする
・行の追加関数は成功するか分からないため、Maybeモナドを返す
という方法が良いかと思うのですが、手続き脳なのでよくわかりません。