2009年10月23日金曜日

Haskell の代数的データ型を比較、特定の基準でソート – compare, sortBy

Ruby であるクラスのオブジェクトを比較可能にするには、クラスに Comparable モジュールをインクルードする。Python なら __cmp__ メソッドをクラスに実装
同じように Haskell でも代数的データ型を比較できるようにするには、Ord クラスのインスタンスにする。

比較できるように

代数的データ型の定義
例えば、「人」が「名前」「年齢」を持つことを代数的データ型で表現すると、
data Person = Person { name :: String
                     , age  :: Int
                     } deriving Show

Ord クラスのインスタンスにする
Data.Ord によると、
Minimal complete definition: either compare or <=. Using compare can be more efficient for complex types.
よって、compare メソッドを実装。ただし、ここでは「人」を比較可能にしたとき、その「年齢」のみで順序が決まるものとする。
instance Ord Person where
       compare x y = compare (age x) (age y)
比較対象の「年齢」を表わす age は Int 型で、これは既に Ord 型のインスタンスなので compare メソッドで比較した結果をそのまま返した。

Eq クラスのインスタンスにする必要も
しかし、このままではエラーが表示されてしまう。 (+_+)
    No instance for (Eq Person)
      arising from the superclasses of an instance declaration
Ord クラスは以下のように Eq クラスを継承している。そのため、Person 型は Eq のインスタンスでなくてはならない。
class Eq a => Ord a where
(Data.Ord より)
例えば、同じ年齢なら同値とみなすとしておくなら、
instance Eq Person where
    x == y = age x == age y
(単に名前も含めて同値とするなら、Person 型の定義において導出インスタンスを使い deriving (Show, Eq) のようにする。)
具体的な値で比較してみる。
*Main> Person "Tarou" 30 < Person "Hanako" 30
False
*Main> Person "Tarou" 30 <= Person "Hanako" 30
True
*Main> Person "Tarou" 30 < Person "Hanako" 10
False
*Main> Person "Tarou" 30 > Person "Hanako" 10
True

ソート

Data.Listsort の定義は、
sort :: Ord a => [a] -> [a]
Person 型を Ord クラスのインスタンスにしたので、[Person] に sort を適用できるようになった。ps を以下のように定義して、
ps = [ Person "Saburou" 30
     , Person "Jiro" 20
     , Person "Tarou" 10
     , Person "Hanako" 30
     ]
ソートすると、
*Main> sort ps
[Person {name = "Tarou",   age = 10},
 Person {name = "Jiro",    age = 20},
 Person {name = "Saburou", age = 30},
 Person {name = "Hanako",  age = 30}]

特定の基準でソート

しかし、上記のように定義した場合、インスタンス宣言したときの比較に固定されてしまう。色々な基準でソートしたいなら、Data.ListsortBy 関数で比較方法を引数として渡してソート。
例えば、名前で比較させたい場合、
sortBy (\x y -> compare (name x) (name y)) ps
順序を逆にしたい場合は、x と y を入れかえて、
sortBy (\x y -> compare (name y) (name x)) ps

comparing 関数
Data.Ord には、こういうときに便利な comparing 関数が定義されている。
comparing p x y = compare (p x) (p y)
これを使うと、
sortBy (comparing name) ps
と書くことができる。

flip で逆順
順序を逆にしたい場合は、flip 関数を使い引数を入れかえる。
sortBy (flip $ comparing name) ps

複数の基準でソート
次に、「年齢順に並べるが、同じ年齢の場合は名前順にしたい」のなら、
  print $ sortBy cmp ps where
                 cmp x y = let c = comparing age x y
                           in if c /= EQ then c
                              else comparing name x y

複数の基準をつなげる

ここで、「人」の属性に「性別」も加える。
data Gender = Male | Female deriving (Show, Eq, Ord)

data Person = Person { name   :: String
                     , age    :: Int
                     , gender :: Gender
                     } deriving Show
「性別、年齢、名前」の順にソートするなら、
  print $ sortBy cmp ps where
                 cmp x y = let c = comparing gender x y
                           in if c /= EQ then c
                              else let c = comparing age x y
                                   in if c /= EQ then c
                                      else comparing name x y
先ほどの [Person] 型のリストの内容を以下のように変更。
ps = [ Person "Youko"   30 Female
     , Person "Saburou" 30 Male
     , Person "Jiro"    20 Male
     , Person "Hanako"  30 Female
     , Person "Tarou"   10 Male
     ]
これを上記でソートした結果、
[Person {name = "Tarou",   age = 10, gender = Male},
 Person {name = "Jiro",    age = 20, gender = Male},
 Person {name = "Saburou", age = 30, gender = Male},
 Person {name = "Hanako",  age = 30, gender = Female},
 Person {name = "Youko",   age = 30, gender = Female}]

つなげる関数

それにしても、上記のコードは let, if, let, if,… と長い。 (+_+) これを 「Haskell の State モナド (1) - 状態を模倣する」のように、つなぎの部分を部品化しておき、個々のパーツをくっつけることはできないだろうか?
イメージとしては、次のような形。
  print $ sortBy cmp ps where
                 cmp = comparing gender `comb` 
                       comparing age    `comb` 
                       comparing name

つなぎの関数名を comb とする。最初の二つの関数 comparing gender, comparing age に注目。この二つを引数に取ることを想像すると、
comb cmp1 cmp2 = ...
comparing gender 関数は、比較のための引数を二つ取るので、
comb cmp1 cmp2 = ...             cmp1 x y 
cmp1 の結果を変数に束縛する。
comb cmp1 cmp2 = ...     let c = cmp1 x y 
cmp1 で x, y を引数として取るには、x, y が与えられている必要があるので、無名関数の形で、
comb cmp1 cmp2 = \x y -> let c = cmp1 x y 
cmp1 において比較した結果、同値と見なされなかったら、その比較をこの関数の結果とする。
comb cmp1 cmp2 = \x y -> let c = cmp1 x y 
                         in if c /= EQ then c
そうでなければ、cmp2 で比較する関数を結果とする。
comb cmp1 cmp2 = \x y -> let c = cmp1 x y 
                         in if c /= EQ then c else cmp2 x y

これで先ほどの comb でつなげた関数を実行できるようになる。結果は、
[Person {name = "Tarou",   age = 10, gender = Male},
 Person {name = "Jiro",    age = 20, gender = Male},
 Person {name = "Saburou", age = 30, gender = Male},
 Person {name = "Hanako",  age = 30, gender = Female},
 Person {name = "Youko",   age = 30, gender = Female}]