C# 9.0でHaskellの代数的データ型(ADT)的な書き方をする

# TL; DR

- C# 9.0ではHaskellのADT的な書き方ができて、しかも構文的に軽量
- record構文と継承を用いることで実現
- pretty print や、値に基づいた等価性比較も自動でついてくる

# 概要

2年前、私は [C#にも代数的データ型(ADT)を軽量に定義できる構文がほしい](https://qiita.com/yuchiki1000yen/items/07c109bc8511667c9689)の中で以下のように書いていました。

> C#7, C#8 に入った機能追加によって、 C#でもADTっぽい値の処理が簡潔に書けるようになりました。
しかし、他の言語のADT定義構文と比較すると、C#ではADTっぽい型を定義するために必要な記述量が大変多いです。

そちらの記事ではADT的なコードの書き方を

1. ADT的な構造の定義
2. ADT的な値の作成
3. ADT的な値の使用

に分けて捉えています。そちらの記事を書いた時点では「C# 8.0では ADT的な値の作成・使用は容易だが、 ADT的構造の定義が構文的に重い」という感想を抱いていました。
しかし、この記事を書いたのちにリリースされたC# 9.0では、 1の「ADT的な構造の定義」を用意するところが容易に書けるようになりました。

# ADTとは?

enumが複雑になったようなデータ構造で、 再帰的なデータを容易に記述することができます。HaskellやOCamlなどの言語でよく用いられます。詳しくは[Wikipedia](https://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B) の記事か、以前私が　[C#にも代数的データ型(ADT)を軽量に定義できる構文がほしい#事前知識：代数的データ型(ADT)]( https://qiita.com/yuchiki1000yen/items/07c109bc8511667c9689#%E4%BA%8B%E5%89%8D%E7%9F%A5%E8%AD%98%E4%BB%A3%E6%95%B0%E7%9A%84%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8Badt)で書いた説明をご覧ください。

# ADT的な書き方の例

例として、四則演算の数式を保持し、必要に応じてそれを計算するシチュエーションを想定します。

この記事では、まず表したい対象がなんであるのかを定義します。つぎに先ほど説明した

1. ADT的な構造の定義
2. ADT的な値の作成
3. ADT的な値の使用

の分類に従い、

1. 数式を表すデータ構造の定義
2. 具体的な数式という値の作成
3. その数式を使用して計算する関数の作成

の順番で書き方を紹介していきます。
最後に、他の言語のADTと呼ばれるものがよく持っている機能のいくつかを、recordが持っていることを紹介します。


## 今回表すデータ構造(数式)

今回表したい数式のデータは以下のBNFで表されるものです。

`e ::= i | e + e | e - e | e * e | e / e`

このBNFは今回扱う数式が

- 整数
- 数式 + 数式
- 数式 - 数式
- 数式 * 数式
- 数式 / 数式

のいずれかの形をしていることを意味しています。たとえば以下のようなものです。

- 1
- 2 + 3
- (1 + 2) * (6 / 2)


## 1. 数式を表すデータ構造の定義

数式の型名を `Expr` (Expression の略)とします。今回の構造は以下のようにコードで記述することができます。

```csharp
abstract record Expr();
sealed record CInt(int value) : Expr;
sealed record Add(Expr left, Expr right) : Expr;
sealed record Sub(Expr left, Expr right) : Expr;
sealed record Mul(Expr left, Expr right) : Expr;
sealed record Div(Expr left, Expr right) : Expr;
```

[record](https://docs.microsoft.com/ja-jp/dotnet/csharp/language-reference/builtin-types/record)はC# 9.0で導入された構造です。classに似ていますが、classと比較すると以下が暗黙のうちに実装されているように振る舞います。

- field/propertyを初期化するconstructor
- pretty printする `toString` メソッド
- 値に基づいた等価性としてオーバーロードされた `==` 演算子
- [deconstruct メソッド](https://docs.microsoft.com/ja-jp/dotnet/csharp/fundamentals/functional/deconstruct#user-defined-types)


続くセクションの中でこれらの特徴を確認していきます。

## 2. 具体的な数式という値の作成

`3 * 2 + 20 / 5` という数式を表す Expr型の値は以下のように作成できます。

```csharp
Expr myExpr =
    new Add(
        new Mul(
            new CInt(3),
            new CInt(2)),
        new Div(
            new CInt(20),
            new CInt(5)));
```

普通のclassのconstructorに値を渡しているように見えると思います。この書き方で対応するfieldへ値を格納するところまでが行われたのと同様に振る舞います。

## 3. その数式を使用して計算する関数の作成

Expr型の値を受け取って、その計算結果の整数を返す `calc` 関数を以下のように定義します。

```csharp
        static int calc(Expr expr) => expr switch
        {
            CInt(var i) => i,
            Add(var l, var r) => calc(l) + calc(r),
            Sub(var l, var r) => calc(l) - calc(r),
            Mul(var l, var r) => calc(l) * calc(r),
            Div(var l, var r) => calc(l) / calc(r),
            _ => throw new InvalidOperationException("unreachable")
        };
```

型switch機能を用いて上のように書けます。Deconstructメソッドが定義したかのように、各ケースにおいて分解代入が使えています。

## recordが持っているその他の特徴

### Pretty Print

以下のコードはmyExprを表示するコードです。

```csharp
Expr myExpr =
    new Add(
        new Mul(
            new CInt(3),
            new CInt(2)),
        new Div(
            new CInt(20),
            new CInt(5)));

Console.WriteLine(myExpr);
```

実行すると、

```
Add { left = Mul { left = CInt { value = 3 }, right = CInt { value = 2 } }, right = Div { left = CInt { value = 20 }, right = CInt { value = 5 } } }
``` 

が表示されます。
細かい表示の方式は異なりますが、 Haskell では `deriving(Show)` で似たようなことができます。

### 値に基づく等価性

以下を実行した結果はtrueになります。これは、recordでは、参照ではなく値に基づいた比較を `==` がするからです。

```csharp
Expr myExpr1 =
    new Add(
        new Mul(
            new CInt(3),
            new CInt(2)),
        new Div(
            new CInt(20),
            new CInt(5)));

Expr myExpr2 =
    new Add(
        new Mul(
            new CInt(3),
            new CInt(2)),
        new Div(
            new CInt(20),
            new CInt(5)));

Console.WriteLine(myExpr1 == myExpr2);
```
Haskellだと、 `deriving(Eq)` が同様の機能を提供します。

# C# 8.0 のときとの比較

データ構造の定義のところで大きく違いが出ています。

C# 9.0 では、このデータ構造は以下のように定義できました。

```csharp
abstract record Expr();
sealed record CInt(int value) : Expr;
sealed record Add(Expr left, Expr right) : Expr;
sealed record Sub(Expr left, Expr right) : Expr;
sealed record Mul(Expr left, Expr right) : Expr;
sealed record Div(Expr left, Expr right) : Expr;
```

これをC# 8.0 以前の書き方で書くと、等価性周りの実装を全て省いても以下のように長大なコードになってしまいます。

```csharp
class Expr {}
class CInt : Expr {
    public int Value { get; }
    public CInt(int value) => Value = value;
    public void Deconstruct(out int value) => value = Value;
    public override string ToString() => $"CInt({Value})";
}
class Add : Expr {
    public Expr Left { get; }
    public Expr Right{ get; }
    public Add(Expr l, Expr r) => (Left,Right) = (l, r);
    public void Deconstruct(out Expr l, out Expr r) => (l, r) = (Left, Right);
    public override string ToString() => $"Add({Left}, {Right})";
}
class Sub : Expr {
    public Expr Left { get; }
    public Expr Right{ get; }
    public Sub(Expr l, Expr r) => (Left,Right) = (l, r);
    public void Deconstruct(out Expr l, out Expr r) => (l, r) = (Left, Right);
    public override string ToString() => $"Sub({Left}, {Right})";
}
class Mul : Expr {
    public Expr Left { get; }
    public Expr Right{ get; }
    public Mul(Expr l, Expr r) => (Left,Right) = (l, r);
    public void Deconstruct(out Expr l, out Expr r) => (l, r) = (Left, Right);
    public override string ToString() => $"Mul({Left}, {Right})";
}
class Div : Expr {
    public Expr Left { get; }
    public Expr Right{ get; }
    public Div(Expr l, Expr r) => (Left,Right) = (l, r);
    public void Deconstruct(out Expr l, out Expr r) => (l, r) = (Left, Right);
    public override string ToString() => $"Div({Left}, {Right})";
}
```

recordを用いると簡潔に書けることがお分かりいただけるかと思います。

# 参考: scalaの case class

今回紹介した record と非常によく似た機能として、 scalaには case class/ case object というものがあります。
case classの用いられ方の例をみると、C# で recordをこのように用いることはそれほど突飛な発想ではないことが分かるかと思います。

## 用いられ方の例

- [tour of scala パターンマッチング](https://docs.scala-lang.org/ja/tour/pattern-matching.html)
- [scala-text.github.io/scala_text ケースクラスとパターンマッチング](https://scala-text.github.io/scala_text/case-class-and-pattern-matching.html)
- [scala exercises - case classes](https://www.scala-exercises.org/std_lib/case_classes)

# まとめ

C# 9.0ではHaskellのADT的な書き方ができ、しかもC#8.0の時と比べると構文的にはるかに軽量になっています。これはC# 9.0 で導入されたrecord構文のおかげです。Haskellの `deriving(Show, Eq)` 相当の特徴も、自前実装することなく使うことができます。

[前回の記事](https://qiita.com/yuchiki1000yen/items/07c109bc8511667c9689)を書いた時から比べると C#は遙かに便利になったように思われます。これからもC#の進化に目を離せません。

今回用いたコードは[こちら](https://github.com/yuchiki/csharp-nine-adt)にあります。