対象とする聴衆のレベル

• Intermediate: 分野の基礎知識を持っている

※競技プログラミングの知識については必要ありません

セッションのテーマ

• 理論

(理論に近いかな?)

セッションの概要

多くのアルゴリズムやデータ構造は、命令型プログラミングを前提に解説されていることが多いです。
アルゴリズム内部で使われるデータ構造は破壊的な変更が可能なことが前提であるため、短命データ構造が前提になります。また、プログラミング言語の抽象化能力には焦点を当てていないものが殆どで、Haskell のように、永続データ構造が備わっていて抽象化能力の高い言語でそのアルゴリズムを実装する場合、どのような抽象に至るのか解説されていることは希です。

私は競技プログラミングを Haskell で嗜んでおり、そのため様々なアルゴリズムを Haskell で実装しています。 Haskell でアルゴリズムを実装すると、その他の言語で実装したときには得られなかった様々なメンタルモデルでアルゴリズムを見ることができるようになり、結果、よりよい抽象に辿り着くことができることが多くあります。また、それをそのメンタルモデルそのままに実装することができるのも、関数型言語ならではと思っています。

例えば動的計画法を、代数的構造で抽象化することができます。 セグメント木はモノイドによって抽象化できることが知られていますが、Haskell ならそれをより自然な形で実装することができます。深さ優先探索や幅優先探索は、状態空間を宣言し、状態を遷移させる高階関数 f を渡すだけで様々な問題を解くことができるよう、実装することができます。よりよい抽象に至ると、より幅広い問題を一つの実装で解くことができます。

本セッションでは、幾つかのアルゴリズムの実装とその抽象を紹介し、命令型プログラミングと関数型プログラミングでの計算に対するメンタルモデルの違いを浮き彫りにすることを目標にします。