[解決済み] 関数型言語における「パターンマッチング」とは？

質問

関数型プログラミングについて読んでいて、次のことに気づきました。 パターンマッチング は、関数型言語の中核機能の一つとして多くの記事で言及されています。

Java/C++/JavaScriptの開発者のために、どういう意味か説明できる人がいますか？

どのように解決するのですか？

パターンマッチングを理解するには、3つの部分を説明する必要があります。

1. 代数的なデータ型。
2. パターンマッチとは
3. その凄さの理由

代数的データ型の簡単な説明

MLライクな関数型言語では、離散結合型と呼ばれる単純なデータ型を定義することができます。これらのデータ構造は，単純なコンテナであり，再帰的に定義することが できます．例えば

type 'a list =
    | Nil
    | Cons of 'a * 'a list

はスタックのようなデータ構造を定義しています。このC#と同等と考えてください。

public abstract class List<T>
{
    public class Nil : List<T> { }
    public class Cons : List<T>
    {
        public readonly T Item1;
        public readonly List<T> Item2;
        public Cons(T item1, List<T> item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}

で、その Cons と Nil 識別子は単純なクラスを定義します。 of x * y * z * ... は、コンストラクタといくつかのデータ型を定義しています。コンストラクタのパラメータは無名で、位置とデータ型によって識別されます。

のインスタンスを作成します。 a list クラスのようなものです。

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

と同じである。

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil()))));

パターンマッチの簡単な説明

パターン・マッチは一種のタイプ・テストである。つまり、上のようなスタックオブジェクトを作ったとすると、以下のようにスタックをpeekしたりpopしたりするメソッドを実装することができます。

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

let pop s =
    match s with
    | Cons(hd, tl) -> tl
    | Nil -> failwith "Empty stack"

上記のメソッドは、以下のC#と同等です（そのように実装されてはいませんが）。

public static T Peek<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return hd;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

public static Stack<T> Pop<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return tl;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

(ほとんどの場合、ML言語はパターンマッチングを実装しています。 なし このため、C#のコードは多少ごまかしが効いています。実装の詳細については、手のひらを返すような形で脇に置いておきましょう :) )

データ構造の分解を簡単に説明

よし、peekメソッドに戻ろう。

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

コツは hd と tl の識別子は変数です。). もし s は、型 Cons という変数に束縛します。 hd と tl .

パターンマッチングが便利なのは、データ構造をその 形状 の代わりに 内容 . そこで、2分木を次のように定義することを想像してください。

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

を定義することができます。 ツリーローテーション を以下のように設定します。

let rotateLeft = function
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
    | x -> x

let rotateRight = function
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c))
    | x -> x

(その let rotateRight = function のシンタックスシュガーです。 let rotateRight s = match s with ... .)

つまり、データ構造を変数に束縛するだけでなく、それをドリルダウンすることもできるのです。例えば、あるノードがあるとしよう let x = Node(Nil, 1, Nil) . もし rotateLeft x をテストします。 x を最初のパターンにマッチさせると、右の子の型が Nil ではなく Node . 次のパターンに移るよ。 x -> x これはどんな入力にもマッチし、修正されないまま返される。

比較のために、上記のメソッドをC#で書くと、次のようになる。

public abstract class Tree<T>
{
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc);

    public class Nil : Tree<T>
    {
        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nilFunc();
        }
    }

    public class Node : Tree<T>
    {
        readonly Tree<T> Left;
        readonly T Value;
        readonly Tree<T> Right;

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }

        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nodeFunc(Left, Value, Right);
        }
    }

    public static Tree<T> RotateLeft(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => r.Match(
                () => t,
                (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr))));
    }

    public static Tree<T> RotateRight(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => l.Match(
                () => t,
                (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r))));
    }
}

真剣に取り組むために

パターンマッチはすごい

何かを実装することができます 似たような を使って、C#でパターンマッチを行うことができます。 ビジターパターン しかし、複雑なデータ構造を効果的に分解することができないため、柔軟性に欠ける。 さらに、パターンマッチを使う場合 コンパイラは、大文字と小文字を区別してくれます。 . なんて素晴らしいんでしょう。

C#やパターンマッチのない言語で、同様の機能をどのように実装するか考えてみてください。実行時にテストテストやキャストをせずにどうやるか考えてみてください。確かに 固い ただ、面倒でかさばるだけです。 また、コンパイラがすべてのケースをカバーしているかどうかを確認することもできません。

そのため、パターンマッチングは、非常に便利でコンパクトな構文でデータ構造を分解し、ナビゲートするのに役立ち、コンパイラが ロジック を、少なくとも少しは使ってみてください。それは本当に は はキラー機能です。