Scalaで型レベル”だけ”でクイックソート | POSTDScalaの型システムが先進的であることは、皆さんもご存じのことかと思います。この投稿では、Scalaの型システムのみを使った クイックソート アルゴリズムの実装方法をご紹介したいと思います。なお、ここで紹介するデモの完全なコードは こちら をご覧ください。 自然数 まずは準備から。ソートアルゴリズムを実装するには、ソートする対象が必要ですよね。ここでは自然数を用います。もちろん、Scalaの型システムには利用可能な自然数はありません。そんなわけで、全ての自然数の型を作る必要があります。 型を無限に作るというのは、恐らく時間の浪費になるでしょうから、ここはもう少し賢い手を考えます。そう、数学を使いましょう。 ペアノの公理 ペアノの公理とは、自然数を形式的に定義するためのシンプルな方法のことです。 0 は特別なものとする。 0 は自然数である。 全ての自然数 n には、それに続くもう1つ別の
