代数的データ型

このページでは、Haskell における代数的データ型について説明します。

代数的データ型とは

代数的データ型 (algebraic data type) は、図みたいに木構造で表現される値からなるデータ型です。 配列のような一部の例外は別とすれば、Haskell で取り扱うあらゆるデータ型は代数的データ型です。

代数的データ型

もう少しきちんと説明すると、代数的データ型は項 (term) の形をとるデータ型をいいます。 別の言葉でいえば、ランクのある木構造をとるデータ型とも言えます。

データ型の定義

次のプログラムは、図形を表すデータ型 Shape と、図形の面積を求める関数 area を定義したものです。 ここでは、図形として長方形を考えています。

data Shape = Rect Double Double

area :: Shape -> Double
area (Rect x y) = x * y

main = print $ area (Rect 2 3)  -- 出力: 6.0

キーワード data で始まる宣言は data 宣言と呼ばれ、新しい型を定義するために使われます。 data 宣言で定義されるデータ型は、代数的データ型です。

このプログラムで定義される Shape型構成子 (type constructor)、Rectデータ構成子 (data constructor) と呼ばれます。 両者は英字の大文字 (A-Z) で始めなければなりません。 なお、型構成子とデータ構成子には、同じ名前を使用することができます。

ひとつの型に複数のデータ構成子を定義することもできます。 次のプログラムは、長方形と三角形を表すデータ構成子からなるデータ型を定義した例です。

data Shape = Rect Double Double  -- 長方形
           | Tri  Double Double  -- 三角形

area :: Shape -> Double
area (Rect x y) = x * y
area (Tri  x y) = x * y / 2

main = do print $ area (Rect 3 4)  -- 出力: 12.0
          print $ area (Tri  3 4)  -- 出力: 6.0

代数的データ型は、列挙型みたいな使い方もできます。 次のプログラムは、曜日を表すデータ型 DayOfWeek とそれを扱う関数を定義した例です。

data DayOfWeek = Mon | Tue | Wed | Thu | Fri | Sat | Sun

holiday :: DayOfWeek -> Bool
holiday Sat = True
holiday Sun = True
holiday _   = False

main = do
  print $ holiday Sun  -- 出力: True
  print $ holiday Mon  -- 出力: False

そして、代数的データ型は多相型にすることもできます。 次のプログラムは、タプルを模した型 Tuple とそれを扱う関数を定義した例です。

import Prelude hiding (fst)  -- 標準関数の fst を隠すおまじない

data Tuple a b = Tuple a b

fst :: Tuple a b -> a
fst (Tuple a _) = a

main = print $ fst (Tuple 123 456)  -- 出力: 123

フィールドラベル

次の data 宣言は、人を表す型 Person を定義したものです。

data Person = Person String Int  -- Person 名前 年齢

この宣言を次のように書き換えると、フィールドに名前を与えることができます。

data Person = Person { name :: String, age :: Int }

name, ageフィールドラベル (field label) と呼ばれ、フィールドへのアクセサの役割を果たします。

data Person = Person { name :: String, age :: Int }

taro = Person { name = "Taro", age = 25 }

main = do print $ name taro  -- 出力: "Taro"
          print $ age taro   -- 出力: 25

フィールドラベルをもつ代数的データ型は、次のプログラムに示すように、フィールドの名前を指定して値を取り出すパターンを書くことができます。 (もちろん、ふつうの代数的データ型と同じようにパターンを書いて、値を取り出すこともできます。)

data Person = Person { name :: String, age :: Int }

intro :: Person -> String
intro (Person { name = n }) = "My name is " ++ n ++ "."

taro = Person "Taro" 25

main = putStrLn $ intro taro   -- 出力: My name is Taro.

フィールドラベルをもつ代数的データ型は、フィールドの一部を変えたデータを作る操作が簡単にできます。 例えば、人の年齢を更新する関数 inc が次のように書けます。

data Person = Person { name :: String, age :: Int }

inc :: Person -> Person
inc p = p { age = age p + 1 }

taro = Person "Taro" 25

main = print $ age $ inc taro   -- 出力: 26

再帰的データ型

次のプログラムは、リストを模した型 List を定義したものです。 例えば、型 List Int[Int] に相当し、値 Cons 1 (Cons 2 (Cons 3 Nil))[1, 2, 3] に相当します。

import Prelude hiding (length)  -- 標準関数の length を隠すおまじない

data List a = Nil | Cons a (List a)

length :: List a -> Int
length Nil         = 0
length (Cons x xs) = 1 + length xs

main = do print $ length Nil                             -- 出力: 0
          print $ length $ Cons 1 (Cons 2 (Cons 3 Nil))  -- 出力: 3

型シノニム

次のように type 宣言を用いると、型シノニム (type synonym) を定義できます。 type 宣言によって宣言された型シノニムは、元の型と区別されません。

type String = [Char]

型変数が含まれる場合、type 宣言は次のように書かれます。

type Triple a b c = (a, b, c)

newtype 宣言

newtype 宣言は、データ構成子数 1、フィールド数 1 の型専用の data 宣言とでも言うべきもので、既存の型をラップした型を与えます。

newtype 宣言で定義された型は元の型と区別されますが、元の型と同じ内部表現で扱われます。 このため、data 宣言で全く新しい型を定義するよりはプログラムを軽くできるという利点があります。

次のプログラムは、"0123" のような数字列を表す型 DigitString を定義したものです。 関数 atoi は、数字列を整数に変換する関数です。 引数が数字列であるべきことを強調するために、String 型ではなく DigitString 型の値を引数に要求します。

newtype DigitString = DigitStr String

atoi :: DigitString -> Int
atoi (DigitStr xs) = read xs

main = print $ atoi (DigitStr "0123")  -- 出力: 123

中置データ構成子

データ構成子には、コロン : で始まる演算子を使うこともできます。

次のプログラムは、有理数を表す型 Ratio を定義したものです。

data Ratio = Integer :/ Integer

ratioToFloat :: Ratio -> Float
ratioToFloat (x :/ y) = fromIntegral x / fromIntegral y

main = do print $ ratioToFloat (3 :/ 2)   -- 出力: 1.5
          print $ ratioToFloat (10 :/ 3)  -- 出力: 3.33...

ちなみに、標準の有理数型、複素数型は、次のように定義されています(実際には他の制約が付きます)。

data Ratio a   = a :% a
data Complex a = a :+ a

標準の代数的データ型

標準で定義されているあらゆるデータ型も、代数的データ型とみなすことができます。

例えば、Bool 型は次のように定義された代数的データ型です。

data Bool = False | True

Int 型は、次のように定義された代数的データ型とみなせます。 (実際にはこのようなコードは書けませんが…。)

data Int = ... | -2 | -1 | 0 | 1 | 2 | ...

タプル型は、要素数の異なるタプルごとに data 宣言があります。

data (,)   a b     = (,)   a b
data (,,)  a b c   = (,,)  a b c d
data (,,,) a b c d = (,,,) a b c d
...

リスト型は、次のように再帰的に定義されます。

data [] a = [] | a : [a]

Maybe 型もオーソドックスな代数的データ型のひとつです。

data Maybe a = Nothing | Just a