ソートの双対性 - Qiita

備忘録に近いので、well containedな内容にはなっていません。というより、リンク集に近い。 あとでもうちょっと本を読んで付け足すかも。 はじまり なんでか忘れたけどkinabaさんのブログの過去記事 を読んでたときに、これはいわゆる「双対性」ではと気づく。 →"duality sort"とかでググる。 →ビンゴ http://www.cs.ox.ac.uk/ralf.hinze/publications/Sorting.pdf 論文の二章 https://ja.wikipedia.org/wiki/%E5%A7%8B%E4%BB%A3%E6%95%B0 にあるような感じで、リストや木などのデータ構造はある関手に関する始代数として定義できる。 Haskellのコードが載っているので、実際に入力しながら確かめると良い。 型がすごく読みにくいので頑張る必要がある。 三章 普通のソートさ