C++17でパターンマッチ

C++ 17でパターンマッチを行うライブラリを作りました。

# 背景

C++23以降に向けてパターンマッチの導入が検討されているようです[^1]。これはScalaやRustなどの言語にある仕組みで、入力データの型や構造をもとにプログラムの動作を決めるものです。従来の`swtich`文をより宣言的な書き方にしたり、`std::optional`や`std::variant`をより扱いやすくしたりすることが期待されます。

[^1]: https://cppmap.github.io/standardization/cppx/#_4

C++17でパターンマッチを使えるライブラリがないか探してみたところ、[match(it)](https://github.com/BowenFu/matchit.cpp) や [MPark.Patterns](https://github.com/mpark/patterns) というライブラリが見つかりました。構文がキレイで使いやすそうです。

こういうものを見て、自分でも何か作ってみたいと思いました。

# 成果物

[Github](https://github.com/Yosh31207/Easy-Matching) に上げました。

https://github.com/Yosh31207/Easy-Matching

# 動作確認環境

GCC 11.3.0

# 使い方

詳細はGithubのREADMEを参照してください。ここではざっくりと紹介します。

## 基本

本ライブラリの構文は前述のmatch(it)やMPark.Patternsに強く影響を受けています。

基本の構文は以下の形です。

```C++
match(VALUE)(
    pattern | PATTERN1 = HANDLER1,
    pattern | PATTERN2 = HANDLER2,
    ...
)
```

ハンドラは以下のいずれかを指定します。

* 変数
* 引数なしの関数オブジェクト
* マッチした値を引数とする関数オブジェクト

例えば階乗計算は以下のような感じに書くことができます。

```C++
#include "easymatch/easymatch.hpp"

using namespace easymatch;

// 階乗計算
constexpr int factorial(int n) {
    return match(n)(
        pattern | 0 = 1,
        pattern | _ = [](auto x) { return x * factorial(x - 1); }
    );
}
```

値の範囲により条件分けする場合は以下のように書きます。

```C++
#include "easymatch/easymatch.hpp"

#include <string>

using namespace easymatch;
using std::to_string;

std::string check_value(int n) {
    return match(n)(
        pattern | (_ <    0) = [](int x) { return to_string(x) + " is negative.";         },
        pattern | (_ <  100) = [](int x) { return to_string(x) + " is lower than 100.";   },
        pattern | 100        = [](int x) { return to_string(x) + " is 100.";              },
        pattern | _          = [](int x) { return to_string(x) + " is greater than 100."; }
    );
}
```

関数は値を返す必要はありません。標準出力に出力するのが目的であれば以下のように書けます。

```C++
void check_value(int n) {
    match(n)(
        pattern | (_ <    0) = [](int x) { std::cout << x << " is negative.";         },
        pattern | (_ <  100) = [](int x) { std::cout << x << " is lower than 100.";   },
        pattern | 100        = [](int x) { std::cout << x << " is 100.";              },
        pattern | _          = [](int x) { std::cout << x << " is greater than 100."; }
    );
}
```

## std::optionalのマッチ

値のあるなしに応じて`some`または`none`にマッチさせることができます。

```C++
#include "easymatch/easymatch.hpp"

#include <optional>
#include <string>

using namespace easymatch;
using namespace std::string_literals;
using std::string;
using std::to_string;
using std::optional;
using std::nullopt_t;

std::string check_optional(const std::optional<int>& value) {
    return match(value)(
        pattern | some = [](int x)     { return "holds value: "s + to_string(x); },
        pattern | none = [](nullopt_t) { return "holds nullopt"s; }
    );
}
```

## std::variant, std::anyのマッチ

`as<T>`を使って型ごとのマッチングができます。各ハンドラの関数にはマッチした型のパラメータが渡されます。

```C++
#include "easymatch/easymatch.hpp"

#include <string>
#include <variant>

using namespace easymatch;
using std::string;
using std::to_string;

std::string check_variant(const std::variant<int, double, std::string>& value) {
    return match(value)(
        pattern | as<int> = [](auto&& x) {  // intが渡される
            return to_string(x) + " is int.";
        }, 
        pattern | as<double> = [](auto&& x) { // doubleが渡される
            return to_string(x) + " is double.";
        }, 
        pattern | as<string> = [](auto&& x) {  // stringが渡される
            return x + " is string.";
        }
    );
}
```

`std::any`の場合も同様です。`std::any`は`std::variant`と違って任意の型を保持しえるので、何にもマッチしなかった場合に失敗しないよう、最後に`_`を置くことを推奨します。

```C++
#include "easymatch/easymatch.hpp"

#include <any>
#include <string>
#include <string_view>

using namespace easymatch;
using std::any;
using std::string;

constexpr std::string_view check_any(const std::any& value) {
    return match(value)(
        pattern | as<int>    = std::string_view("holding int"),
        pattern | as<double> = std::string_view("holding double"),
        pattern | as<string> = std::string_view("holding string"),
        pattern | _          = std::string_view("holding unknown")
    );
}
```

最初の方に書いたとおり、ハンドラには引数を取る関数、引数なしの関数、値のいずれかを指定することができます。この例では値を書いていますが、`std::variant`の例と同様に、マッチした型を引き取る関数を渡すこともできます。

## 複数の値のマッチ

`ds` を使って可変個の値をマッチさせることができます。`ds`はdestructureの略です。以下のようになります。

```C++
#include "easymatch/easymatch.hpp"

#include <string_view>

using namespace easymatch;
using std::string_view;

constexpr std::string_view check_numbers(int a, int b, int c) {
    // 入力が7ならtrueを返し、それ以外ならfalseを返す関数
    constexpr auto is_seven = [](auto x) {
        return x == 7;
    };

    return match(a, b, c)(
        pattern | ds(1, 2, 3       ) = string_view("1, 2, 3"),
        pattern | ds(1, 2, _ <   0 ) = string_view("1, 2, negative"),
        pattern | ds(1, 2, _ > 100 ) = string_view("1, 2, large"),
        pattern | ds(1, 2, _       ) = string_view("1, 2, _"),
        pattern | ds(1, _, 1       ) = string_view("1, _, 1"),
        pattern | ds(_, _, 1       ) = string_view("_, _, 1"),
        pattern | ds(7, is_seven, 7) = string_view("7, 7, 7"),
        pattern | _                  = string_view("otherwise")
    );
}
```

普通に使う分には `(7, is_seven, 7)` のところは素直に `(7, 7, 7)` としておくのが良いと思います。この例では、関数を使ってマッチさせることができることを示すためにこのような書き方にしました。

`std::tuple`も`ds`を使ってマッチさせることができます。以下は上の例と同じように動きます。

```C++
#include "easymatch/easymatch.hpp"

#include <string_view>
#include <tuple>

using namespace easymatch;
using std::string_view;

constexpr std::string_view check_numbers_from_tuple(const std::tuple<int, int, int>& value) {
    constexpr auto is_seven = [](auto x) { return x == 7; };
    return match(value)(
        pattern | ds(1, 2, 3       ) = string_view("1, 2, 3"),
        pattern | ds(1, 2, _ <   0 ) = string_view("1, 2, negative"),
        pattern | ds(1, 2, _ > 100 ) = string_view("1, 2, large"),
        pattern | ds(1, 2, _       ) = string_view("1, 2, _"),
        pattern | ds(1, _, 1       ) = string_view("1, _, 1"),
        pattern | ds(_, _, 1       ) = string_view("_, _, 1"),
        pattern | ds(7, is_seven, 7) = string_view("7, 7, 7"),
        pattern | _                  = string_view("otherwise")
    );
}
```

`ds` でマッチさせた結果は関数の引数として受け取ることができます。

```C++
#include "easymatch/easymatch.hpp"

#include <iostream>
#include <tuple>

using namespace easymatch;

void tuple_handler(int a, int b, int c) {
    match(a, b, c)(
        // マッチした結果を引数として受け取る
        pattern | ds(0, 1, _ < 0) = [](int x, int y, int z) {
            std::cout << x << " is zero\n";
            std::cout << y << " is one\n";
            std::cout << z << " is negative\n";
        },

        // マッチした結果をタプルとして受け取る
        pattern | ds(0, 1, _ < 10) = [](const std::tuple<int, int, int>& z) {
            std::cout << std::get<0>(z) << " is zero\n";
            std::cout << std::get<1>(z) << " is one\n";
            std::cout << std::get<2>(z) << " is lower than 10\n";
        },

        // 引数なしのラムダ式も使用可
        // この例では入力値 {a, b, c} をラムダ式にキャプチャさせて受け取っている
        pattern | ds(0, 0, _ < 20) = [&]() {
            std::cout << std::get<0>(a) << " is zero\n";
            std::cout << std::get<1>(b) << " is zero\n";
            std::cout << std::get<2>(c) << " is lower than 20\n";
        },

        pattern | _ = [] {
            std::cout << "not matched";
        }
    );
}
```

## パターンの組み合わせ

パターン同士は`|`で連結させることができます。

```C++
#include "easymatch/easymatch.hpp"

#include <optional>
#include <string_view>

using namespace easymatch;
using std::optional;
using std::string_view;

constexpr std::string_view check_large(const std::variant<int, double, std::string_view, std::optional<int>>& x) {
    constexpr auto is_large_str = [](std::string_view x) {
        return x.size() > 20;
    };

    return match(x)(
        pattern | as<int>           | when(_ >= 100)        = string_view("large int"),
        pattern | as<int>           | _                     = string_view("small int"),
        pattern | as<double>        | when(_ >= 100)        = string_view("large double"),
        pattern | as<double>        | _                     = string_view("small double"),
        pattern | as<string_view>   | when(is_large_str)    = string_view("large string"),
        pattern | as<string_view>   | _                     = string_view("small string"),
        pattern | as<optional<int>> | some | when(_ >= 100) = string_view("large optional<int>"),
        pattern | as<optional<int>> | some | _              = string_view("small optional<int>"),
        pattern | as<optional<int>> | none                  = string_view("nullopt"),
        pattern | _                                         = string_view("otherwise")
    );
}
```

`when`は中身がパターンであることを示すためのラッパーです。この例では`when`はなくても動きますが、これがフィルタとして働くことを示すために意図的に付けています。

## 複雑な例

`ds`と`some`, `any`を組みわあせた場合の例です。ハンドラにはマッチした結果が渡されるため、`std::optional`は有効値または`nullopt`に、`std::variant`は保持している型にアンラップされます。

```C++
std::string unwrap_tuple(std::optional<int> a, const std::variant<int, std::string>& b) {
    return match(a, b)(
        pattern | ds(some, as<int>) = [](int x, int y) {
            std::stringstream ss;
            ss << "a: " << x << " is value; b: " << y << " is int";
            return ss.str();
        },

        pattern | ds(some | when(_ < 0), as<std::string>) = [](int x, const std::string& y) {
            std::stringstream ss;
            ss << "a: " << x << " is value and negative; b: " << y << " is string";
            return ss.str();
        },

        pattern | ds(some | _, as<std::string>) = [](int x, const std::string& y) {
            std::stringstream ss;
            ss << "a: " << x << " is value and non-negative; b: " << y << " is string";
            return ss.str();
        },

        pattern | ds(none, as<int> | when(_ < 0)) = [](nullopt_t, int y) {
            std::stringstream ss;
            ss << "a is nullopt; b: " << y << " is negative int";
            return ss.str();
        },

        pattern | ds(none, as<int> | _) = [](nullopt_t, int y) {
            std::stringstream ss;
            ss << "a is nullopt; b: " << y << " is non-negative int";
            return ss.str();
        },

        pattern | ds(none, as<std::string>) = [](nullopt_t, const std::string& y) {
            std::stringstream ss;
            ss << "a is nullopt; b: " << y << " is string";
            return ss.str();
        },

        pattern | _ = [] { return std::string("not matched"); }
    );
}
```

# その他のパターンについて

c++23以降で提案されているパターンマッチ構文や、前述の [match(it)](https://github.com/BowenFu/matchit.cpp), [MPark.Patterns](https://github.com/mpark/patterns) では更に多くのパターンを提供しています。パターンマッチに興味を持った人はこれらも参考にすると勉強になると思います。

例えば、match(it)ではマッチした結果を受け取るためのIdentifier Patternという仕組みがあり、以下のようなことができます。

```C++
#include "matchit.h"
constexpr bool symmetric(std::array<int32_t, 5> const& arr)
{
    using namespace matchit;
    Id<int32_t> i, j; 
    return match(arr)(
        pattern | ds(i, j, _, j, i) = true,
        pattern | _                 = false
    );
}
```

逆に、この仕組みのためにマッチ結果をハンドラの引数として渡すことができず、マッチ結果はIdentifierを介して受け取るか、ラムダ式にキャプチャさせる必要があります[^2]。個人的には、上例の `i, j` のような一時的な変数を介すよりも、ラムダ式の引数で受け取る方がよりシンプルだと感じたので、自ライブラリではそのような形としました。

[^2]: ヘルパを使うことでラムダ式の引数として受け取ることもできるようです（[参考](https://github.com/BowenFu/matchit.cpp/issues/68)）。

# 参考

本ライブラリは以下のライブラリの影響を受けました。

* [match(it)](https://github.com/BowenFu/matchit.cpp)
* [MPark.Patterns](https://github.com/mpark/patterns)

また、パターンマッチの考えについては以下の記事が参考になりました。

https://qiita.com/hinastory/items/87431aa48197cc4d7d84

# 感想

C++でテンプレートメタプログラミングするのは楽しいですね。また、他の言語で使われているパターンマッチという仕組みを知れたこと自体も個人的に勉強になりました。