maxValue = maximize . static . prune 5 . gameTree第三回 : 高階関数と進化するデータ型
第一回では、インクリメンタル開発について、および 非侵入的 な状態を保つことの重要性について述べました。今回は、前回の最後の状態からコードの変更を行います。
各段階の重なり
コードの変更は、我々が 侵入的 であると宣言した対象ですが、最後に追加した分を変更することは許容されます。
コードに変更を入れることの問題点は、それに依存しているその他すべてのコードが危険にさらされる可能性があることです。これこそが 侵入的 であると言われる所以です。最後 に追加した分に依存しているコードはおそらく存在しないため、安全に変更することができます。
理屈はともかく、与えられた盤面のミニマックス値を求めるために入れた最後の追加分を見てみましょう。
これはうまく動くのですが、もっと関数型 らしく してみようと思います。
関数型プログラマは非常に早い段階で抽象化を導入したがること、また上記のコードには隠れた抽象が存在することはすでに見たとおりです。ここでは、盤面の木を Double 値の木にマップしていますが、木の構造はそのまま残ります。このことは ファンクタ と呼ばれる抽象化の性質です。ファンクタに対しては、現在の構造を保ったまますべての要素に関数 f を適用する一般された関数 fmap を使用することができます。つまり今回の Tree 型はこのようなファンクタなのです。
ファンクタとしての木の性質を使うために、static の代わりに fmap f を使います。
static を fmap static とする一般化
evaluateBy f = maximize . fmap f . prune 5 . gameTree
maxValue = evaluateBy staticevaluateBy はパラメータ f を取るようになったことに注意しましょう。盤面を引数として取り、maximize が要求する Ord を返すような関数なら何であっても f として与えることができます。
evaluateBy のような、他の関数をパラメータとして取る関数は 高階関数 と呼ばれます。高階関数は関数型プログラミングでは非常によく使用され、実際に過去の記事でも以前から特に注意もなく使ってきました。しかし今回のケースは一味違います。ここでは、非常に広く用いられる関数型機能であるところの高階関数を、非侵入的な追加開発 のお膳立てのために使用したのです。
新要件あらわる : 未来予測
ゲームで遊ぶのは楽しいものですが、ときどきコンピュータが、なぜそんな選択をしたのか理解しがたい手を打つように見えることがあります。コンピュータが何を考えているかについて推察し、それを明らかにすることができたら面白いのではないでしょうか。このためのアイデアとして、予測、すなわちゲームが進行した結果としてコンピュータが考える最終的な盤面を表示してみます。
コンピュータが自身の勝ちを知っている状態
この目的のために、ミニマックス値を与える盤面を見つける必要があります。結果としてこちらのほうが予測よりも簡単です。evaluateBy を使いますが、しかしもう static を渡すことはしません。その代わり、盤面を静的な評価値だけでなく、評価値と盤面自身との 組 にマップする関数を渡します。
静的な値と盤面を組にする
endValue = evaluateBy capture where
capture board = (static board, board)いい感じです。まず何より、完全に 非侵入的 な追加になっています！ 既存のコードは全く変更していません。
次に、このコードは高階関数を用いており、新しい要件を見越していたわけではないにもかかわらず、関数型のスタイルに則った非常に自然な結果になっています。
しかしこのままでは問題があり、コンパイルできません。
我々が作成したマッピング関数は Ord を返す必要がありますが、組は (実際には任意のタプルは) 要素すべてがやはり Ord であるときのみ Ord になります。Double 値は Ord ですが、Board 型はそうではありません。
むむ、次にどうしましょう？ Board の定義まで戻って変更しますか？ この場合、侵入的 な変更になります。
ここで Frege の型クラス (いわば Java のインタフェースに相当) が持つ大きな利点が登場します。データ型を進化させる ことができるのです！ 新しくコードを追加することにより、Board は完全に静的な型の安全性を保ったまま Ord 型クラスのインスタンスになります！
すべての盤面が等しいとみなす以外、付け加えるロジックはありません。組を順序付けるために必要なのは、組に対して statid 関数が返す Double 値だけです。
盤面はみな平等に創られており……
instance Ord Board where (<=>) a b = EQこのコードはかなり単純に見えますが、大きな意味を内包しています。Board を Ord のインスタンスにするために、Board 型に新たな機能を付け加えています！
これで全体がコンパイルできて動くようになりました。 リンク先 でゲームをプレイすると予測が効いているのがわかります。
次の回では、さらに思い切った拡張を適用します。安全な並列実行です。