型クラスについて
型クラス(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 = y
class (Eq a) => Ord a where
となっているのは,OrdがEqのサブクラスであることを意味する.このため(==)や(/=)を定義する必要はない
compareはEQ(等しい),LT(小さい),GT(大きい)のどれかを返す関数である.compareか(<=)だけ定義すればあとはデフォルトメソッドが対応してくれる.max(min)は2つの引数をとり,大きな(小さな)方を返すメソッドである.
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 b
Functorクラスは写像可能な型の型クラスである.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の6つだけである.
2分木の例
data Tree a = Leaf a | Branch a (Tree a) (Tree a)
このような2分木の型を考える.例えばこの木のノードの数を計算する関数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
2分木の各ノードの値が同じであれば同じ木であると考えると,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))