Haskellのnewtypeとdataの違い


今回はデータ型を定義する`newtype`と`data`の違いについて説明していきます。主に違いを探っていくので`data`や`newtype`の詳しいオプションなどは説明していません。この記事で使用しているGHCのバージョンは8.8.3です。

## data

まずは`data`です。データ型を定義するためのキーワードです。

```haskell
data Alpha = A Int
data Beta a = B Int
```

`data Beta`の後ろの`a`は**型引数**です。これがあるかないかで、カインドが変わってきます。`B 10`の型は`Beta a`で、`A 10`は`Alpha`になっています。`A`は値コンストラクタで、`Int`を受け取って`Alpha`の値を生成します。

```haskell
Prelude> :k Alpha
Alpha :: *
Prelude> :k Beta
Beta :: * -> *
Prelude> :t A
A :: Int -> Alpha
Prelude> :t B
B :: Int -> Beta a
Prelude> :t A 10
A 10 :: Alpha
Prelude> :t B 10
B 10 :: Beta a
```

また、フィールド(値の種類)を複数持てます。

```haskell
data Bool = False | True
data GalileanMoon = Io | Europa | Ganymede | Callisto
```

`Bool`は`True`か`False`で、`GalileanMoon`の型を持つ値は4つの衛星のうちのどれか、ということです。

## newtype

`newtype`は値コンストラクタが**1つ**で、フィールド(値の種類)も**1つだけ**です。`newtype`は常に`data`で置き換えられますが、その逆は常に可能ではありません。[HLint](https://github.com/ndmitchell/hlint)は、`data`で宣言されたそういった(コンストラクタも値も1つの)型を見つけたら「`newtype`で置き換えられるけど、どう?」と聞いてくれます。

```haskell
.\data.hs:2:1: Suggestion: Use newtype instead of data
Found:
  data Alpha = A Int
Perhaps:
  newtype Alpha = A Int
Note: decreases laziness
```

先程の`Alpha`と`Beta`は`newtype`で置き換えられます。

```haskell
newtype Alpha = A Int
newtype Beta a = B Int
```

## 主な違い

|                  | data       | newtype              |
| ---------------- | ---------- | -------------------- |
| 型引数           | いくつでも | 複数可                |
| レコード構文     | できる     | できる               |
| フィールド       | いくつでも | 1つ                  |
| 値コンストラクタ | いくつでも | 1つ                  |
| パフォーマンス   | 型による   | 基本的にdataより高速 |

### 評価戦略

`newtype`ではフィールドは1つしかないため、`Alpha _`のようなパターンマッチの場合、中身は無視されます。

`undefined`は、計算を失敗させて例外を投げる多相定数です。

```haskell
Prelude> :t undefined
undefined :: a
Prelude> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries\base\GHC\Err.hs:80:14 in base:GHC.Err
  undefined, called at <interactive>:2:1 in interactive:Ghci1
```

これを`data`と`newtype`で実装した別々の型で試してみましょう。

#### dataの正格性オプション

`data`には、値コンストラクタの引数を評価することを強制するオプションがあります。`!`を値の先頭につけ、それを評価することをコンパイラに強制します。[Haskell Wiki](https://wiki.haskell.org/Keywords#.21)の`!`の部分に簡単な説明があるので読んでみます。

>Whenever a data [constructor](https://wiki.haskell.org/Constructor) is applied, each argument to the constructor is evaluated if and only if the corresponding type in the algebraic data[type](https://wiki.haskell.org/Type) declaration has a strictness flag, denoted by an exclamation point. For example:
>
>```haskell
> data STList a
>         = STCons a !(STList a)  -- the second argument to STCons will be
>                                 -- evaluated before STCons is applied
>         | STNil
>```

>値コンストラクタが適用される際に、代数的データ型の宣言が感嘆符であらわされるフラグがついている場合は、各引数がコンストラクタに評価されます。例:
>
>```haskell
> data STList a
>         = STCons a !(STList a)  -- STConsの第2引数は
>                                 -- STConsが適用される前に評価される
>         | STNil
>```
>
>to illustrate the difference between strict versus lazy constructor application, consider the following:
>
>```haskell
> stList = STCons 1 undefined
> lzList = (:)    1 undefined
> stHead (STCons h _) = h -- this evaluates to undefined when applied to stList
> lzHead (h : _)      = h -- this evaluates to 1 when applied to lzList
>```

>正格なコンストラクタと遅延するコンストラクタの違いを説明するには、次の例を考えましょう:
>
>```haskell
> stList = STCons 1 undefined
> lzList = (:)    1 undefined
> stHead (STCons h _) = h -- stListに適用すると、undefinedと評価されます
> lzHead (h : _)      = h -- lzListに適用すると、1が返ります。
>```

2つ目の例がわかりやすいですね。`STCons`は正格なコンストラクタなので`stList`の適用中に`undefined`を評価しなければならなくなって失敗しますが、`lzList`はリストの残りを無視して1を返します。

このフラグを使って、`data`と`newtype`をテストしてみます。

#### パターンテスト

ソースコードとテスト関数に結果をコメントしたものです。

```haskell

data A1 = A1 Int
data A2 = A2 !Int
newtype B1 = B1 Int

f1 = case A1 undefined of
    A1 _ -> 1 -- 1

f2 = case A2 undefined of
    A2 _ -> 1 -- undefined

f3 = case B1 undefined of
    B1 _ -> 1 -- 1

g1 = case undefined of
    A1 _ -> 1 -- undefined

g2 = case undefined of
    A2 _ -> 1 -- undefined

g3 = case undefined of
    B1 _ -> 1 -- 1

i :: Int
i = undefined -- undefined

gInt = case i of
    _ -> 1 -- 1
```

見ると、`newtype`で宣言した型は2つのテストでどちらも1を返しています。正格なコンストラクタの`A2`は、1つ目でコンストラクタの引数を無視する`A1`に比べてより評価が厳しくなっています。

表にまとめます。

|                                | data        | !data       | newtype |
| ------------------------------ | ----------- | ----------- | ------- |
| `case C undefined of C _ -> 1` | `1`         | `undefined` | `1`     |
| `case undefined of C _ -> 1`   | `undefined` | `undefined` | `1`     |

例えば、こんな関数があるとき、

```haskell
function :: B1 -> String
function (B1 _) = "works"
```

この関数には`(B1 undefined)`を与えてもちゃんと`"works"`が返ってきます。`newtype`は**値の種類が1つしかない**ので、型を見ればコンストラクタが値の中身を評価せずにパターンマッチを通せるのです。

### パフォーマンス[^2]

正格性フラグ(!)を使うと`data`のスペースリークは抑えられるようです。[^1]ただし、

> If your datatype has a single constructor with a single field, use a `newtype` declaration instead of a `data` declaration.  The `newtype` constructor will be optimised away.
> もしデータ型が単一のコンストラクタしか持っていないなら、`newtype`を`data`の代わりに使いましょう。`newtypes`コンストラクタは最適化されます。

`newtype`は型をほどく際のオーバーヘッドが軽減されるため、`data`よりも高速になります。

> Haskell provides the `newtype` keyword, for the construction of unlifted types. Pattern-matching on a newtype constructor doesn't do any work, ...  so every value in the type is wrapped in the constructor.
> Haskellはリフトされていない型のために、`newtype`キーワードを提供しています。`newtype`コンストラクタはパターンマッチでは何もしません。... 全ての型の中の値はコンストラクタに包まれます。

[Real World HaskellのWeb版](http://book.realworldhaskell.org/read/using-typeclasses.html)に有識者のコメントがありました。

> ... The NewType constructor is only used at compilation time, then deleted. ...
> ... NewTypeコンストラクタはコンパイル時にのみ使われ、削除されます。...

つまりランタイムでは`newtype`で包まれた値は裸の値として扱われているわけです。`data`と違って複数の値を扱う必要がないため、速くなるわけです。

## まとめ

- `data`は値を複数定義できるけど、`newtype`は1つだけ
- `newtype`は`data`よりも使い方の制約が厳しい
- `newtype`で定義した型の値は処理系ではコンストラクタを除いた裸の値として扱われている
    - よって、型コンストラクタは引数を評価されずにパターンマッチが通る
    - また、型をほどく際のオーバーヘッドが軽減されて`newtype`は比較的高速になる

## 感想

すごいH本の`newtype`のパートではあまり解説が詳しくなく、インターネット上でも日本語の文献が少なく、苦労しました。見る限り、`HLint`を通してみたりソースコードを眺めたりして特別な理由がなければ`newtype`で置き換えるのがよいと思います。

## 参考文献

- Haskell Wiki
    - [Newtype](https://wiki.haskell.org/Newtype)
    - [Keywords/!](https://wiki.haskell.org/Keywords#.21)
    - [Constructor](https://wiki.haskell.org/Constructor)
    - [Performance/Data types](https://wiki.haskell.org/Performance/Data_types)
- [Real World Haskell - Chapter 6. Using Typeclasses](http://book.realworldhaskell.org/read/using-typeclasses.html)

[^1]: [Performance/Data types](https://wiki.haskell.org/Performance/Data_types)より。
[^2]: `newtype`と`data`のパフォーマンスの数値的な比較は発見できませんでした。見つかったら追記します。