Haskell 代数的データ型 超入門

  • 79
    Like
  • 0
    Comment
More than 1 year has passed since last update.

代数的データ型の基本的な使い方を説明します。

シリーズの記事です。

  1. Haskell 超入門
  2. Haskell 代数的データ型 超入門 ← この記事
  3. Haskell アクション 超入門
  4. Haskell ラムダ 超入門
  5. Haskell アクションとラムダ 超入門
  6. Haskell IOモナド 超入門
  7. Haskell リストモナド 超入門
  8. Haskell Maybeモナド 超入門
  9. Haskell 状態系モナド 超入門
  10. Haskell モナド変換子 超入門
  11. Haskell 例外処理 超入門
  12. Haskell 構文解析 超入門
  13. 【予定】Haskell 継続モナド 超入門
  14. 【予定】Haskell 型クラス 超入門
  15. 【予定】Haskell モナドとゆかいな仲間たち
  16. 【予定】Haskell Freeモナド 超入門
  17. 【予定】Haskell Operationalモナド 超入門
  18. 【予定】Haskell Effモナド 超入門
  19. 【予定】Haskell アロー 超入門

練習の解答例は別記事に掲載します。

この記事には応用編があります。

この記事には@shigemk2さんによるScala版があります。

代数的データ型

以下の3つを合わせて代数的データ型と呼びます。

  1. 列挙型(他言語のenumに相当)
  2. 直積型(他言語のstructに相当)
  3. 直和型(他言語のunionに相当)

これらを1つずつ見ていきます。

列挙型

種類を区別するための型です。他言語のenumに相当します。

data Color = Blue | Red | Green | White

この例でのColorを型(型構築子)、Blueなどをコンストラクタ(データ構築子)と呼びます。

※ コンストラクタは構築子と訳されます。用語は括弧書きの型構築子やデータ構築子と呼ばれることが一般的です。ここではオブジェクト指向言語での慣例に従いカタカナ表記として、用語は以下の記事に合わせています。

命名規則

型とコンストラクタは大文字で始める必要があります。

小文字で始めるとエラーになります。

NG-型
data color = Blue | Red | Green | White
エラー内容
Malformed head of type or class declaration: color
NG-コンストラクタ
data Color = blue | Red | Green | White
エラー内容
Not a data constructor: `blue'

※ 変数・関数が小文字始まりなのと対になる仕様です。

Show

自分で定義した型はそのままではprintで表示できません。

NG
data Color = Blue | Red | Green | White

main = do
    print Blue
エラー内容
No instance for (Show Color) arising from a use of `print'
Possible fix: add an instance declaration for (Show Color)
(略)

型定義の最後にderiving Showを追加すれば表示できるようになります。

OK
data Color = Blue | Red | Green | White deriving Show

main = do
    print Blue
実行結果
Blue

derivingにより自分で定義した型に機能が追加できます。機能を表す部分(Show)は型クラスと呼ばれます。標準で指定できる型クラスは6種類ですが、後でBoolの定義とともに掲載します。

Enum

型クラスEnumを指定すれば数値と相互変換できるようになります。

関数名 機能 備考
fromEnum 列挙型 → 数値 0始まり
toEnum 数値 → 列挙型 ::で変換する型を指定、範囲外はエラー

例を示します。複数の型クラスを指定するには括弧で囲みます。

data Color = Blue | Red | Green | White deriving (Show, Enum)

main = do
    print $ fromEnum Blue
    print $ fromEnum Red
    print $ fromEnum Green
    print $ fromEnum White
    print (toEnum 0 :: Color)
    print (toEnum 1 :: Color)
    print (toEnum 2 :: Color)
    print (toEnum 3 :: Color)
実行結果
0
1
2
3
Blue
Red
Green
White

※ 演算子の優先順位の関係上、::は括弧で囲む必要があります($ではなく)。

Bool

真偽値を表すBoolは標準ライブラリ(Prelude)で定義された列挙型です。

定義
data Bool = False | True deriving (Eq, Ord, Enum, Read, Show, Bounded)

標準で指定できる6種類の型クラスがすべて指定されています。

型クラス 概要
Eq ==/=で比較できます。
Ord 順番を持ちます。<>で大小比較できます。
Read 文字列から変換できます。
Bounded 最小値と最大値を持ちます。

※ 具体的な使用例については、今回の範囲を超えるため詳細は省略します。

練習

【問1】光の三原色と、2つの色を混合する関数mixを定義してください。混ぜることによってできる色も定義の対象とします。ただし同じ成分同士は強め合わないものとします。

ヒント: mix Blue Red = Magenta, その他の色 Green | Cyan | Yellow | White

解答例

直積型

内部に値を持つ型です。他言語の構造体に相当します。馴染みのない用語かもしれませんが、集合論に由来します。

構文

data  = コンストラクタ [フィールドの型 ...]

型とコンストラクタは同名でも別名でも構いません。

同名の例を示します。

data Point = Point Int Int deriving Show

offset (Point x1 y1) (Point x2 y2) =
    Point (x1 + x2) (y1 + y2)

main = do
    let a = Point 2 3
        b = Point 1 1
        c = offset a b
    print c
実行結果
Point 3 4

フィールドの値はパターンマッチで取り出します。名前による方法はレコード構文として後述します。

直積

何が積なのかというイメージを説明します。

先ほどの例でPoint 3 4というのは、34が組み合わさって1つのデータを構成しています。これを3*4のような因数の組み合わせで1つの項を構成しているように捉えます。

集合論による説明は次の記事を参照してください。

newtype

フィールドが1つだけの直積型はnewtypeという別のキーワードで定義できます。

構文
newtype  = コンストラクタ フィールドの型
newtype Foo = Foo Int

内部処理の違いからdataよりも高速に動作するため、フィールドが1つだけならnewtypeで定義した方が良いとされています。dataとは評価タイミングなど細かい部分で違いがありますが、通常ほとんど意識する必要はありません。参考リンクを置いておきます。

練習

【問2】x,y,w,hを表現したRect型を定義して、RectPointが含まれるかどうかを判定する関数containsを実装してください。

具体的には以下のコードが動くようにしてください。

main = do
    print $ contains (Rect 2 2 3 3) (Point 1 1)
    print $ contains (Rect 2 2 3 3) (Point 2 2)
    print $ contains (Rect 2 2 3 3) (Point 3 3)
    print $ contains (Rect 2 2 3 3) (Point 4 4)
    print $ contains (Rect 2 2 3 3) (Point 5 5)
実行結果
False
True
True
True
False

解答例

直和型

列挙型にフィールドを付加することで、複数の直積型を定義したものです。列挙型と直積型の両方の特徴を併せ持っています。

構文
data  = コンストラクタ [フィールドの型 ...] | コンストラクタ [フィールドの型 ...] [| ...]
data Foo = Bar Int Int | Baz Int Int Int

この名前も集合論に由来します。複数の直積型の和だと捉えれば、イメージしやすいかもしれません。

  • Bar Int Int | Baz Int Int Int → Int*Int + Int*Int*Int

※ C言語では共用体に相当しますが、C言語のように共用体のフィールドを選ぶことで解釈を変えることはできません。区別が保持されるという意味合いでF#では判別共用体と呼びます。

サンプル

data Test = TestInt Int
          | TestStr String
          deriving Show

foo (TestInt  1 ) = "bar"
foo (TestStr "1") = "baz"
foo _             = "?"

main = do
    print $ foo $ TestInt  0
    print $ foo $ TestInt  1
    print $ foo $ TestStr "0"
    print $ foo $ TestStr "1"
実行結果
"?"
"bar"
"?"
"baz"

関数の引数は同一の型しか受け付けないため、通常は数値Intと文字列Stringの両方を渡すことはできません。この例では代数的データ型を挟むことでどちらも渡せるようにしています。

オブジェクト指向との比較

オブジェクト指向の感覚ではTestが基底クラス、TestIntTestStrが派生クラスに相当します。関数の扱いは基底クラスのメソッドを派生クラスでオーバーライドする感覚に近いです。

Test.java
class TestInt extends Test {
    private int i;
    public TestInt(int i) { this.i = i; }
    public String foo() {
        if (i == 1) return "bar";
        return super.foo();
    }
}

class TestStr extends Test {
    private String s;
    public TestStr(String s) { this.s = s; }
    public String foo() {
        if (s.equals("1")) return "baz";
        return super.foo();
    }
}

abstract class Test {
    public String foo() { return "?"; }
    public static void main(String[] args) {
        System.out.println(new TestInt( 0 ).foo());
        System.out.println(new TestInt( 1 ).foo());
        System.out.println(new TestStr("0").foo());
        System.out.println(new TestStr("1").foo());
    }
}
実行結果
?
bar
?
baz

オーバーロード

この例ではわざわざ型を作らなくてもオーバーロードした方が簡単です。

Test.java
class Test {
    public static String foo() {
        return "?";
    }
    public static String foo(int i) {
        if (i == 1) return "bar";
        return foo();
    }
    public static String foo(String s) {
        if (s.equals("1")) return "baz";
        return foo();
    }
    public static void main(String[] args) {
        System.out.println(foo( 0 ));
        System.out.println(foo( 1 ));
        System.out.println(foo("0"));
        System.out.println(foo("1"));
    }
}
実行結果
?
bar
?
baz

Haskellでも型クラスを自分で定義すればオーバーロードと似たようなことが可能です。型クラスの定義は今回の範囲を超えますが、参考リンクを置いておきます。

リスト

リストは直和型として定義されています。

定義
data [a] = [] | a:[a]

aは型変数と呼ばれ任意の型が入ります。今回の範囲を超えるため詳細は省略します。

後者は再帰的にa:([] | a:[a])と変形できるため、後続要素が無限に続く可能性があります。

  • a:(a:(a: ... ([])))

型シノニム

文字のリストが文字列です。[Char](文字のリスト)にStringという別名を付けています。

定義
type String = [Char]

このような別名を型シノニムと呼びます。synonym同意語・別名という意味です。

練習

【問3】RectPointを2次元と3次元の両方に対応させて、問2のcontainsも対応させてください。

具体的には以下のコードが動くようにしてください。

main = do
    print $ contains (Rect 2 2 3 3) (Point 1 1)
    print $ contains (Rect 2 2 3 3) (Point 2 2)
    print $ contains (Rect 2 2 3 3) (Point 3 3)
    print $ contains (Rect 2 2 3 3) (Point 4 4)
    print $ contains (Rect 2 2 3 3) (Point 5 5)
    print $ contains (Rect3D 2 2 2 3 3 3) (Point3D 1 1 1)
    print $ contains (Rect3D 2 2 2 3 3 3) (Point3D 2 2 2)
    print $ contains (Rect3D 2 2 2 3 3 3) (Point3D 3 3 3)
    print $ contains (Rect3D 2 2 2 3 3 3) (Point3D 4 4 4)
    print $ contains (Rect3D 2 2 2 3 3 3) (Point3D 5 5 5)
実行結果
False
True
True
True
False
False
True
True
True
False

解答例

レコード構文

直積型や直和型のフィールドに名前を付けることができます。これをレコード構文と呼びます。

構文
data  = コンストラクタ { 名前 ::  [, 名前 ::  ...] } [| ...]

フィールド名は小文字で始める必要があります。

data Foo = Foo { bar :: Int, baz :: String }

生成

構文
コンストラクタ { 名前 =  [, 名前 =  ...] }
Foo { bar = 1, baz = "a" }

無名のときと同じ方法でも生成できます。その場合でもprintでは名前が表示されます。

両方の例を示します。

data Foo = Foo { bar :: Int, baz :: String } deriving Show

main = do
    print $ Foo { bar = 1, baz = "a" }  -- 名前を指定して束縛
    print $ Foo 2 "b"                   -- 無名のときと同じ方法
実行結果
Foo {bar = 1, baz = "a"}
Foo {bar = 2, baz = "b"}

フィールド値の取得

フィールド名がそのままフィールド値を取得する関数になります。無名のときと同様にパターンマッチでも取り出せます。レコード構文でパターンマッチすることもできます。

data Foo = Foo { bar :: Int, baz :: String } deriving Show

main = do
    let f = Foo { bar = 1, baz = "a" }
    print f
    print (bar f, baz f)       -- フィールド名を関数として使用
    let (Foo a b) = f          -- パターンマッチで取り出し
    print (a, b)
    let (Foo { bar = c }) = f  -- レコード構文でパターンマッチ
    print c
実行結果
Foo {bar = 1, baz = "a"}
(1,"a")
(1,"a")
1

一部を変更したコピー

Haskellの変数は値を書き換えることができませんが、フィールドも同様です。その代わり一部の値を変更したコピーを生成できます。

構文
変数 { 名前 =  [, 名前 =  ...] }

例を示します。

data Foo = Foo { bar :: Int, baz :: String } deriving Show

main = do
    let f = Foo { bar = 1, baz = "a" }
        g = f   { bar = 2 }  -- barを変更したコピー
    print f                  -- 元のまま
    print g                  -- 変更されたコピー
実行結果
Foo {bar = 1, baz = "a"}
Foo {bar = 2, baz = "a"}

練習

【問4】問2の解答をレコード構文で書き直してください。

解答例

参考

レコード構文は次の記事を参考にしました。

レコード構文を使い倒すためのLensというライブラリがあります。オブジェクト指向のようなことができるようです。