てきとうなメモ

本の感想とか技術メモとか

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 =  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]を返す関数である.

例えばCharはEnumインスタンスである.

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と等価である.

Monad

これはMonadの時に書く.

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))