Haskellの勉強 (7) - 型クラス
型クラスについて
型クラス(type class)とは
quicksortはリストの要素をソートする関数である．
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
++ [x]
++ quicksort [y | y <- xs, y>=x]quicksortを適用されるデータの型は比較可能な型でなければならない．すなわち，(<)や(>=)のような演算が可能でなければならない．では，どのようにquicksortの型を決めれば良いだろうか．全ての型が比較可能であるわけではないので，これはlengthのように[a]で定義することはできない．
length :: [a] -> Int length [] = 0 length (x:xs) = 1 + length xs
そこで，quicksortの型推論してみると
> :t quicksort quicksort :: (Ord a) => [a] -> [a]
となる．
このOrd aはaが比較可能な(順序のある)型であることを意味している．Ordは型クラスであり，(Ord a) => [a] -> [a]は「型クラスOrdのインスタンスaという前提で，aのリストを引数にとり，aのリストを返す関数を意味している．型クラスとはある操作(メソッド)が可能な型を表している．この例ではOrdのメソッドは(<)や(>=)である．型クラスを用いることで様々な型(全てではない)に適用できる汎用的な関数を記述することができる．
型クラス宣言とインスタンス宣言
型クラスは以下のように宣言する．
class Ord a where (<) :: a -> a -> Bool ...
これは，型クラスOrdに属する型aは(<)という関数を定義していなければならないことを意味する．型クラスに属する型のことをその型クラスのインスタンスと呼ぶ．インスタンスは次のように宣言される．
instance Ord Int where x < y = x `intLessThan` y
これは型クラスOrdのインスタンスであるIntの関数'<'の定義はx `intLessThan` yであることを意味している．
次にいくつか基本的な型クラスを紹介する．
Eq
Eqは==(等価)と/=(非等価)メソッドを持つ．
class Eq a where
(==), (/=) :: a -> a -> Bool
-- Minimal complete definition:
-- (==) or (/=)
x /= y = not (x == y)
x == y = not (x /= y)x /= y = not (x == y)
となっているのは(/=)のデフォルトメソッドであり，/=はインスタンス宣言で定義されていなければ==の否定で定義される．'/='と'=='は相補的に定義されており，インスタンスはどちらか一つを定義すれば良い．
Ord
quicksortの例で説明したように比較演算子をメソッドとして持つ．
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
(<), (<=), (>=), (>) :: a -> a -> Bool
max, min :: a -> a -> a
-- Minimal complete definition:
-- (<=) or compare
-- Using compare can be more efficient for complex types.
compare x y
| x == y = EQ
| x <= y = LT
| otherwise = GT
x <= y = compare x y /= GT
x < y = compare x y == LT
x >= y = compare x y /= LT
x > y = compare x y == GT
-- note that (min x y, max x y) = (x,y) or (y,x)
max x y
| x <= y = y
| otherwise = x
min x y
| x <= y = x
| otherwise = yclass (Eq a) => Ord a where
となっているのは，OrdがEqのサブクラスであることを意味する．このため(==)や(/=)を定義する必要はない
compareはEQ(等しい)，LT(小さい)，GT(大きい)のどれかを返す関数である．compareか(<=)だけ定義すればあとはデフォルトメソッドが対応してくれる．max(min)は２つの引数をとり，大きな(小さな)方を返すメソッドである．
Enum
Enumは列挙型を意味する．
class Enum a where
succ, pred :: a -> a
toEnum :: Int -> a
fromEnum :: a -> Int
enumFrom :: a -> [a] -- [n..]
enumFromThen :: a -> a -> [a] -- [n,n'..]
enumFromTo :: a -> a -> [a] -- [n..m]
enumFromThenTo :: a -> a -> a -> [a] -- [n,n'..m]
-- Minimal complete definition:
-- toEnum, fromEnum
--
-- NOTE: these default methods only make sense for types
-- that map injectively into Int using fromEnum
-- and toEnum.
succ = toEnum . (+1) . fromEnum
pred = toEnum . (subtract 1) . fromEnum
enumFrom x = map toEnum [fromEnum x ..]
enumFromTo x y = map toEnum [fromEnum x .. fromEnum y]
enumFromThen x y = map toEnum [fromEnum x, fromEnum y ..]
enumFromThenTo x y z =
map toEnum [fromEnum x, fromEnum y .. fromEnum z]最小定義をするためにはtoEnumという整数型からEnumのインスタンスに変換する関数とその逆のfromEnumの両方を定義すれば良い．
succ(pred)は次(前)の値を返す関数であり，enumFrom, enumFromTo, enumFromThen, enumFromThenToはそれぞれ[x..], [x..y], [x,y..], [x,y..z]を返す関数である．
Prelude> pred 'c' 'b' Prelude> succ 'c' 'd' Prelude> fromEnum 'a' 97 Prelude> fromEnum 'a' 97 Prelude> take 5 $ enumFrom 'a' "abcde" Prelude> enumFromTo 'a' 'e' "abcde" Prelude> take 5 $ enumFromThen 'a' 'c' "acegi" Prelude> enumFromThenTo 'a' 'c' 'e' "ace"
Bounded
Boundedは上限と下限の存在する型を表す．
class Bounded a where
minBound :: a
maxBound :: aここで，minBoundやmaxBoundを評価してもどの型のminBound(maxBound)かわからないのでエラーが発生する．そのため::を用いて型を指定する．
Prelude> minBound::Bool False Prelude> maxBound::Bool True Prelude> minBound::Char '\NUL' Prelude> maxBound::Char '\1114111' Prelude> minBound::Int -2147483648 Prelude> maxBound::Int 2147483647
ReadとShow
Readは文字列からその型に変換するメソッドreadを持ち，Showは型の文字列表現を表すメソッドshowを持つ．実際にinstance宣言するときはもっとややこしいが．
Prelude> read "1" + read "2" 3 Prelude> show 42 "42" Prelude> show [1,2,3] "[1,2,3]"
ghciで式を評価しているときはshowメソッドを用いて値を表示している．そのため，Showのインスタンスではないものはエラーとなり表示できない．
Functor
class Functor f where
fmap :: (a -> b) -> f a -> f bFunctorクラスは写像可能な型の型クラスである．fmapメソッドは汎用的なmap関数であり，例えばリストに対するfmapはmapと等価である．
deriving
わざわざ基本的な型クラスのインスタンス宣言をし，各メソッドを定義することは面倒であるので，以下のように宣言することで自動的に定義することができる．
data Day = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday deriving (Eq, Ord, Enum, Bounded, Show)
すると，各型クラスのメソッドを利用できる．
> Sunday == Sunday True > Sunday /= Sunday False > Sunday < Tuesday True > Sunday > Tuesday False > pred Monday Sunday > succ Monday Tuesday > maxBound::Day Saturday > minBound::Day Sunday > show Sunday "Sunday"
derivingを用いることのできる型クラスはEq, Ord, Enum, Bounded, Show, Readの６つだけである．
２分木の例
data Tree a = Leaf a | Branch a (Tree a) (Tree a)
このような２分木の型を考える．例えばこの木のノードの数を計算する関数lengthTreeは以下のように定義できる
lengthTree :: Tree a -> Int lengthTree (Leaf x) = 1 lengthTree (Branch x l r) = 1 + (lengthTree l) + (lengthTree r)
> lengthTree (Leaf 1) 1 > lengthTree (Branch 1 (Leaf 2) (Leaf 3)) 3
２分木の各ノードの値が同じであれば同じ木であると考えると，TreeはEqのインスタンスとなり，以下のように宣言する．
instance (Eq a) => Eq (Tree a) where
Leaf x == Leaf y = x == y
Branch x l r == Branch x' l' r' = x == x' && l == l' && r == r'
_ == _ = False文字列として表示したいのでShowのインスタンスとして宣言する
instance (Show a) => Show (Tree a) where
show (Leaf x) = "(Leaf " ++ (show x) ++ ")"
show (Branch x l r) = "(Branch " ++ (show x) ++ " " ++ (show l) ++ " " ++ (show r) ++ ")"> Leaf 5 (Leaf 5) > (Branch 1 (Leaf 2) (Leaf 3)) (Branch 1 (Leaf 2) (Leaf 3))
これらはderivingで自動的に定義可能である．
data Tree a = Leaf a | Branch a (Tree a) (Tree a) deriving (Eq,Show)
また，各ノードに関数適用するfmapが定義できるので，Functorのインスタンスとして宣言できる．
instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Branch x l r) = Branch (f x) (fmap f l) (fmap f r)> fmap (\x -> x * x) (Leaf 3) (Leaf 9) > fmap (\x -> x * x) (Branch 1 (Leaf 2) (Leaf 3)) (Branch 1 (Leaf 4) (Leaf 9))
