TL;DR
- アルゴリズムを抽象化すると、写像（
map）と結合（fold）がパラメータとして現れ、実装が似たインタフェースになる。 - 関数型言語は再帰的なデータ構造を基本にしているので、
mapとreduceで多くの問題が解ける。
内容
発表の内容は、発表者が最初から知っていたものではなく、アルゴリズムを Haskell で実装する中で見つけてきたものである。
アルゴリズムの抽象化
競技プログラミングでは、アルゴリズムをあらかじめライブラリにしておく（抽象化しておく）ことが多い。アルゴリズムを抽象化すると、その実装は似たようなインタフェースになる。具体的には、写像（map）と結合（fold）がパラメータとして現れる。写像は各状態を新しい状態に移す関数で、結合は複数の結果を 1 つにまとめる二項演算である。これは関数型言語のメンタルモデルでもある。
幅優先探索
幅優先探索（BFS）は、当初グラフにだけ対応した実装だった。しかし、状態遷移の写像をパラメータとして受け取るようにしたことで、さまざまな問題に応用できるようになった。
動的計画法
動的計画法（DP）は、ナップサック問題のように 2 次元配列で考えることが多い。命令型では可変な 2 次元配列を用意する必要があるが、次元が増えるほど頭が混乱する。DP の問題には部分問題の重複性と部分構造の最適性という特性があるので、状態空間（行）が次の状態に遷移していくと考えればよい。これは fold で実現できる。インタフェースを見ると、DP は半環的な構造を持っている。
なぜ map と reduce で解けるか
関数型言語は、data List a = Nil | Cons a (List a) のような再帰的なデータ構造（代数的データ型）を基本にしている。再帰的なデータ構造に適した最小の操作が、map と reduce（fold）である。map は再帰構造に関数を適用する最小単位であり、reduce は再帰構造を畳み込むパターンの最小単位である。
map と reduce は、Lisp がリストに対する map / reduce で多くの問題を記述できると経験的に見つけたことに始まる。関数型言語の発展とともに他のデータ構造にも適用されるようになり、Haskell がそれらを理論付けて型クラスの階層に取り込んだ。
命令型と関数型
命令型でアルゴリズムを書くときは「どう動かすか」に焦点を当てる。関数型で書くときは「何を意味しているか」に焦点を当てる。
キーワード
自分の理解
発表では BFS も半環で、モナドらしいと触れられていたが、よく分からなかった。