Zenn
🃏

フシギな型の数え上げ - Scala で型の値を並べてみよう

2021/03/01に公開
Scala
math
tech

はじめに

可算集合 (countable set) という言葉を聞いたことがありますか？

これは、大雑把に言えば自然数 (\mathbb{N} = \{ 0, 1, 2, \cdots \}) と一対一に対応付けることができる集合のことです。
例えば、整数全体からなる集合 (\mathbb{Z} = \{ \cdots, -2, -1, 0, 1, 2, \cdots \}) は、一見すると値が両側に広がっていって始点 (下界) も終点 (上界) もありませんが、可算集合の例の1つです。
具体的には [0, -1, 1, -2, 2, \cdots] のように負の数と正の数を交互にして並べることで、自然数と一対一に対応付けられます。
他にも有理数全体からなる集合 (\mathrm{Q} = \{ 1/1, 2/1, 1/2, \cdots \}) もうまく並べることで自然数と一対一に対応付けられるので可算集合である、といった話を聞いたことはないでしょうか。
(中学生の頃の教科書に載っていた気がします)

プログラミング的には、型は取り得るすべての値の集合と考えられます。
そこで、可算集合となる型を考えてみると、意外と多くの型が可算になることが分かります。[1]

  • すべての有限な型 (Boolean や Int など)
  • 整数型 (BigInt)
  • 可算な型のオプション型 (Option[A])
  • 可算な型の直和 (Either[A, B])
  • 可算な型の組 ((A, B))
  • 可算な型のリスト (List[A])
  • 有限な型の集合 (Set[A])
  • 有限な型から可算な型への連想配列 (Map[A, B])
  • 有限な型から可算な型への関数 (A => B)

実は最近、こういった可算な型を扱う uchu というライブラリを開発しています。

https://github.com/MakeNowJust-Labo/uchu

この記事では uchu の開発中に学んだ「可算な型の並べ方」を Scala を使って紹介していきたいと思います。

型の値の並べ方

すべての値を含むような LazyList を作ることで、値の並べ方を確認していきます。
通常の List ではなく LazyList なのは、すごく大きなリストになる可能性があり、すべてを計算することが現実的でないためです。

XXX 型の値を並べた結果を返す関数は enumXXX もしくは finXXX という名前で定義していきます。
また、有限個の値を取る型と区別するために、 Enumerate 型とそれを継承した Finite 型を定義しておき、それで LazyList を包むことにします。

class Enumerate[A](enumerate: LazyList[A])
class Finite[A](enumerate: LazyList[A]) extends Enumerate(enumerate)

有限な型の場合

Boolean は true か false の2つの値だけで、Int は Int.MinValue から Int.MaxValue までの有限個の値しか取りません。
このような場合、単純に並べていけば良いです。

implicit def finBoolean: Finite[Boolean] = new Finite(LazyList(false, true))
implicit def finInt: Finite[Int] =
  new Finite(LazyList.from(Int.MinValue).takeWhile(_ != Int.MaxValue))

整数型 (BigInt) の場合

冒頭で説明したように [0, -1, 1, -2, 2, ...] と並べていきます。
値の上限値・下限値がなく、大きさが無限に (可算無限個) ある LazyList を作っていることに注意してください。[2]

implicit def enumBigInt: Enumerate[BigInt] = {
  val positive = LazyList.iterate(0: BigInt)(_ + 1)
  val negative = LazyList.iterate(-1: BigInt)(_ - 1)
  new Enumerate(positive.zip(negative).flatMap { case (p, n) => Seq(p, n) })
}

また、自然数全体の型として Nat と、これに対する並べ方も定義しておきます。
これは単純に [0, 1, 2, ...] と並べるだけです。

case class Nat(value: BigInt) {
  require(value >= 0)
}

implicit def enumNat: Enumerate[Nat] =
  new Enumerate(LazyList.iterate(0: BigInt)(_ + 1).map(Nat(_)))

オプション型 (Option[A]) の場合

この場合は [None, Some(0), Some(1), ...] のように、None のあとに Some の値を並べていくことになります。

implicit def enumOption[A](implicit A: Enumerate[A]): Enumerate[Option[A]] =
  new Enumerate(LazyList.cons(None, A.enumerate.map(Some(_))))

implicit def finOption[A](implicit A: Finite[A]): Finite[Option[A]] =
  new Finite(enumOption[A].enumerate)

さらに、この型の値の個数がどれくらいになるか考えてみましょう。
なお、このような個数が無限個になる場合は、その個数を集合の濃度といいます。
さて、Option[A] の場合、Some に包まれた値は A の濃度 (|A|) だけあり、それに None が1つ加えられます。
よって、Option[A] の濃度は次のようになります。

|\mathrm{Option}[A]| = |A| + 1

直和型 (Either[A, B]) の場合

ここまでは何も考えずに並べてこれましたが、ここからは うまい並べ方 を考えていかなければいけません。

Either[A, B] の値の並べ方として考えられる一番簡単なアイディアは、[Left(0), Left(1), ..., Right(0), Right(1), ...] のように、左側の値をすべて並べたあとに右側の値を並べる、という方法でしょう。
しかし、この場合左側の値の濃度が無限 (可算無限) だった場合に問題になります。
例えば、Either[Nat, Int] の値 Right(0) は、左側の Nat が可算無限個あるために、自然数の番号を付けることができません。
このような並べ方は、うまい並べ方ではないわけです。

そこで、[Left(0), Right(0), Left(1), Right(1), ...] のように、左側の値と右側の値を交互に並べていくことにします。
こうすることで、自然数の番号をちゃんと与えることができる うまい並べ方 になります。

implicit def enumEither[A, B](implicit A: Enumerate[A], B: Enumerate[B]): Enumerate[Either[A, B]] = {
  def interleave[A](xs: LazyList[A], ys: LazyList[A]): LazyList[A] =
    xs.headOption match {
      case Some(x) => LazyList.cons(x, interleave(ys, xs.tail))
      case None    => ys
    }
  new Enumerate(interleave(A.enumerate.map(Left(_)), B.enumerate.map(Right(_))))
}

implicit def finEither[A, B](implicit A: Finite[A], B: Finite[B]): Finite[Either[A, B]] =
  new Finite(enumEither[A, B].enumerate)

また、Either[A, B] の濃度は2つの和になります。

|\mathrm{Either}[A, B]| = |A| + |B|

組 ((A, B)) の場合

組の場合、最も簡単に考えられるのは [(0, 0), (0, 1), ..., (1, 0), (1, 1), ...] のように、左側の値を固定して、右側の値を増加していき、上限まできたら左側の値を増加させて、右側はリセットする、というような方針でしょう。
しかし、この場合は、右側の値が可算無限個あった場合に、左側の値が増加するケースに辿り付けず問題になります。
この方法を図にすると、次のように値を二次元に配置して、列を順番に並べていく方針に対応しています。

列を順番に並べていく

そこで次の図のように、二次元に配置した値を反対角線状に並べていく方針を考えます。
この場合 [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), ...] のように並びます。

反対角線状に並べていく

この対角線状に並べる実装は、次のようになります。

/** 二次元の `LazyList` で渡された要素を反対角線状に並べた `LazyList` を返す。 */
def diagonal[A](table: LazyList[LazyList[A]]): LazyList[A] = {
  def diagonals(edges: Seq[LazyList[A]], table: LazyList[LazyList[A]]): LazyList[Seq[A]] =
    LazyList.cons(
      edges.flatMap(_.headOption), {
        val nextEdges = edges.map(_.drop(1)).filter(_.nonEmpty)
        table.headOption match {
          case Some(edge) => diagonals(edge +: nextEdges, table.tail)
          case None       => transpose(nextEdges)
        }
      }
    )

  def transpose(edges: Seq[LazyList[A]]): LazyList[Seq[A]] =
    if (edges.isEmpty) LazyList.empty
    else LazyList.cons(edges.flatMap(_.headOption), transpose(edges.map(_.tail).filter(_.nonEmpty)))

  diagonals(Seq(LazyList.empty), table).flatten
}

implicit def enumTuple2[A](implicit A: Enumerate[A], B: Enumerate[B]): Enumerate[(A, B)] =
  new Enumerate(diagonal(A.enumerate.map(x => B.map((x, _)))))

implicit def finTuple2[A](implicit A: Finite[A], B: Finite[B]): Finite[(A, B)] =
  new Finite(enumTuple2[A, B].enumerate)

また、(A, B) の濃度は、2つの積になります。

|(A, B)| = |A| \times |B|

リスト (List[A]) の場合

まずはちょうど n 個の値からなるリストを並べることを考えてみましょう。
これは n = 0 の場合は空リストのみ、n > 1 の場合は A の値と n - 1 個の値のリストの組からリストを構築する、と再帰的にすることで定義できます。

/** 引数の `Enumerate` の計算を遅延させる。 */
def enumDelay[A](xs: => Enumerate[A]): Enumerate[A] =
  new Enumerate(LazyList.cons(xs, LazyList.empty).flatten)

def enumListN[A](n: Nat)(implicit A: Enumerate[A]): Enumerate[List[A]] =
  if (n == Nat(0)) new Enumerate(LazyList(List.empty))
  else {
    val pairs = enumTuple2(A, delay(enumListN[A](Nat(n.value - 1))))
    new Enumerate(pairs.enumerate.map { case (x, xs) => x :: xs })
  }

この場合の濃度は、次のようになります。

|\mathrm{List}_n[A]| = \underbrace{|A| \times \cdots |A|}_{n \textrm{個}} = |A|^n

さて、リスト型はすべての長さのリストの集合と考えられます。

\mathrm{List}[A] = \bigcup_{n=0}^\infty \mathrm{List}_n[A]

この濃度は次の式のようになります。

|\mathrm{List}[A]| = \sum_{n=0}^\infty |A|^n

指数関数の無限和を取っているので |A| = 0 でなければ無限大に発散するのは明らかです。
ですが、この場合に自然数と一対一に対応するようなうまい並べ方はあるのでしょうか？

アイディアの1つとして、二次元の座標 (n, k) を長さ n のリストの k 番目のものと対応付ける、という方法があります。
つまり、次の図のように二次元に配置して、組の場合と同じように反対角線状に並べていくことで、自然数と対応付けられます。

リストを二次元に配置する

これを実装すると、次のようになります。

implicit def enumList[A](implicit A: Enumerate[A]): Enumerate[List[A]] =
  new Enumerate(diagonal(enumNat.enumerate.map(enumListN[A](_).enumerate)))

このようにしてリストはうまく並べられるので可算であり、その濃度も可算無限となります。

集合型 (Set[A]) の場合

集合型の場合、その濃度は A の部分集合の個数なので、次のようになります。

|\mathrm{Set}[A]| = 2^{|A|}

この羃乗なのですが、実は常に |A| よりも真に大きくなります (カントールの定理)。
これの何が問題なのかというと、|A| の濃度が無限 (可算無限) の場合、2^{|A|} はそれよりも大きな無限 (連続体濃度) になってしまうのです。
この連続体濃度は実数全体からなる集合の濃度と同じで、どのように並べても自然数と一対一に対応付けられない値が生じることになります。

幸い |A| が有限の場合は 2^{|A|} も有限になり、うまく並べることができます。
よって A を有限の場合に限定することにしましょう。

集合の表現にはビット列を使うと、簡単に実装できます。
k 桁目のビットが立っている場合に k 番目の値を含む、というようにするわけです。
例えば 10 = \texttt{0b1010} の場合、1番目と3番目の値を含むことになります。

implicit def finSet[A](implicit A: Finite[A]): Finite[Set[A]] = {
  val nats = enumNat.enumerate.map(_.value).takeWhile(A.enumerate.sizeIs >= _.bitLength)
  val bits = nats.map(n => LazyList.range(0, n.bitLength).map(n.testBit))
  new Finite(bits.map(_.zip(A.enumerate).collect { case (true, x) => x }.toSet))
}

連想配列 (Map[A, B]) の場合

Map[A, B] の濃度を考えていきます。
Map[A, B] の値は A のそれぞれの値について、B の値が存在するか抜けているかのどちらかになります。
よって A の k 番目の値に対応する B の値が存在する場合 Some を、抜けている場合は None を入れた大きさ |A| のリストで表現できます。
例えば空の Map() は [None, None] で、 Map(true -> 1) は [None, Some(1)]、Map(false -> 2, true -> 1) は [Some(2), Some(1)] のようになります。
このことから Map[A, B] の濃度は長さ |A| の Option[B] リストと等しいと分かります。

|\mathrm{Map}[A, B]| = |\mathrm{List}_{|A|}[\mathrm{Option[B]}]| = (|B| + 1)^{|A|}

また、集合のときと同様の理由で |A| は有限である必要があります。[3]

長さ n のリストを得る関数はすでに持っているので、それを使って実装できそうです。

implicit def enumMap[A, B](implicit A: Finite[A], B: Enumerate[B]): Enumerate[Map[A, B]] = {
  val lists = enumListN[Option[B]](Nat(A.enumerate.size)).enumerate
  new Enumerate(lists.map(_.zip(A.enumerate).collect { case (Some(y), x) => (x, y) }.toMap))
}

ですが、そのように実装した場合にとある問題が生じます。
Map[Int, Int] を考えてみましょう。
この場合 enumListN で大きさが n = 2^{32} のリストをいきなり生成しなければならず[4]、現実的には1つも値を得ることができません。
しかし、途中で生成されるリストの後ろの方のほとんどの値は None となっていて、これを律儀に求めるのは無駄が多いように感じます。
この部分の生成を省略するにはどうすればいいでしょうか？

そこで、Map[A, B] の濃度の式を (やや強引に) 変形してみます。

\begin{aligned} |\mathrm{Map}[A, B]| &= (|B| + 1)^{|A|} \\ &= 1 - 1 + (|B| + 1)^{|A|} \\ &= 1 + |B| \times \frac{1 - (|B| + 1)^{|A|}}{-|B|} \\ &= 1 + |B| \times \underbrace{\frac{1 - (|B| + 1)^{|A|}}{1 -(|B| + 1)}}_{\textrm{等比数列の和}} \\ &= 1 + |B| \times \sum_{n=0}^{|A|-1} (|B| + 1)^n \end{aligned}

かなり恣意的ですが、|A| の冪乗を 0 から |A| - 1 までの冪乗の総和の形に書き換えることができました。
この冪乗の総和の部分は、どこかで見たことがないでしょうか？

そう、リストの濃度ですね。
リストの濃度では、0 から \infty までの総和になっていましたが、ここでは |A| - 1 までです。
これはつまり、大きさが |A| - 1 以下のリストを表しています。

このことから、Map[A, B] は次の型と一対一に対応付けられます。

\mathrm{Map}[A, B] \simeq \mathrm{Option[(B, \bigcup_{n=0}^{|A|-1} \mathrm{List}_n[Option[B]])]}

実際にどのように対応させられるのか、実装を見てみましょう。

implicit def enumMap[A, B](implicit A: Finite[A], B: Enumerate[B]): Enumerate[Map[A, B]] = {
  val sizes = enumNat.enumerate.takeWhile(A.enumerate.sizeIs > _.value.toInt)
  val lists = new Enumerate(diagonal(sizes.map(enumListN[Option[B]](_).enumerate)))
  val pairs = enumTuple2(B, lists)
  val options = enumOption(pairs).enumerate
  new Enumerate(options.map {
    case Some((x, xs)) =>
      (xs :+ Some(x)).zip(A.enumerate).collect { case (Some(y), x) => (x, y) }.toMap
    case None => Map.empty
  })
}

implicit def finMap[A, B](implicit A: Finite[A], B: Finite[B]): Finite[Map[A, B]] =
  new Finite(enumMap[A, B].enumerate)

重要なのは、リストと組で生成した B の値をリストの末尾に追加しているところです。
こうすることで、すべての Map をちょうど1回ずつ生成できます。

関数 (A => B) の場合

最後に、関数の型 A => B の場合です。
この場合の濃度は、Map のときと同じような理由で、次のような冪乗の形になります。
また同様に |A| は有限でなければいけません。

|A \Rightarrow B| = |B|^{|A|}

大きさが |A| のリストを作る方針にすると、Map と同じ問題が生じるので、Map と同じ方針で無駄を無くしていきます。
|B| = 0 を強引に x + 1 の形にしたいので (|B| - 1) + 1 としたいのですが、それだと |B| = 0 の場合に問題になるので、場合分けをすることにします。
よって、実装は次のようになります。
Scala では Map[A, B] が A => B を継承していることに注意してください。

implicit def enumFunction1[A, B](implicit A: Finite[A], B: Enumerate[B]): Enumerate[A => B] =
  B.enumerate.headOption match {
    case Some(y0) =>
      val maps = enumMap(A, new Enumerate(B.enumerate.tail)).enumerate
      new Enumerate(maps.map(_.withDefaultValue(y0)))
    case None => new Enumerate(LazyList(Map.empty))
  }

implicit def finFunction1[A, B](implicit A: Finite[A], B: Finite[B]): Finite[A => B] =
  new Finite(enumFunction1[A, B].enumerate)

まとめ

様々な可算な型に対して、その具体的な並べ方を紹介しました。
とくに Map では、濃度の代数的な変形を用いて効率的な並べ方を考察しました。
このような考え方は興味深いものだと思います。

冒頭でも少し紹介しましたが、このような可算な型を扱う uchu というライブラリを開発しています。

https://github.com/MakeNowJust-Labo/uchu

このライブラリでは、型のすべての値を並べるのに加えて、次のような機能があります。

  • 自然数から、対応する番号の値を取得 (get)
  • 値から、その値の番号の自然数を取得 (indexOf)
  • より正確な関数への対応 (この記事の実装だと「関数を引数に取る関数」のような場合に上手く動作しない)
  • cats の各種データ (Ior, NonEmptyList など) への対応
  • shapeless による、自作の型に対する実装の自動導出

なので、例えば Byte => Byte 型の恒等関数に対応する自然数を得たり、その自然数から恒等関数を復元したりできます。

import codes.quine.labo.uchu._

val index = Universe[Byte => Byte].indexOf(identity[Byte])
// index: Nat = 32316989949542683662948423725997111124203863869193410384466994817863035801811917228340334281644687504736062911011567644519213805233423842768021845337183529314646311447548336600253889511592981262750220262897340499665570156515318251438408729784985563020459930353740998257242847290201416154330386411160207445090734118768302175014759323858241575818130725407196909157134301242080592196854484613569469800849840705388286569844821480735465005100777153377701583675393389674260512954875895654042174314772713333052993889826046594836877197679878261031303911606816379002276861789208548536066964084933538597785629078737585826758400

Universe[Byte => Byte].get(index)
// res0: Option[Byte => Byte] = Some(MapFunction(<function1>, HashMap(69 -> -35, 138 -> 69, 101 -> -51, 249 -> -125, 234 -> 117, 88 -> 44, 170 -> 85, 115 -> -58, 217 -> -109, 5 -> -3, 202 -> 101, 120 -> 60, 247 -> -124, 10 -> 5, 56 -> 28, 142 -> 71, 153 -> -77, 174 -> 87, 185 -> -93, 42 -> 21, 24 -> 12, 37 -> -19, 25 -> -13, 52 -> 26, 14 -> 7, 184 -> 92, 110 -> 55, 125 -> -63, 196 -> 98, 157 -> -79, 189 -> -95, 20 -> 10, 46 -> 23, 93 -> -47, 152 -> 76, 228 -> 114, 57 -> -29, 78 -> 39, 29 -> -15, 216 -> 108, 164 -> 82, 179 -> -90, 106 -> 53, 238 -> 119, 121 -> -61, 84 -> 42, 211 -> -106, 253 -> -127, 147 -> -74, 61 -> -31, 221 -> -111, 132 -> 66, 1 -> -1, 74 -> 37, 206 -> 103, 89 -> -45, 133 -> -67, 116 -> 58, 243 -> -122, 248 -> 124, 220 -> 110, 102 -> 51, 233...

まだリリースはしていませんが、もし面白いと思ってもらえたら GitHub のリポジトリの方にスターをお願いします。
喜びます。

それでは、最後まで記事に目を通していただきありがとうございました。

脚注

  1. そもそも現実のコンピュータで動いている以上全部有限ですが‥‥。 ↩︎

  2. 実は BigInt は 2^\mathtt{Int.MaxValue} までしか表現できないのですが、普通のコンピュータでそこまで到達できることはまずないので、現実的には無限個あるものとして考えることにします。 ↩︎

  3. 厳密には |B| = 0 の場合 |A| が可算無限個あろうと空 Map しか存在できないので Map[A, B] も可算なのですが、それを区別する型を作るのは面倒なので実装では A は Finite であることを要請しています。 ↩︎

  4. 実際には A.enumerate.size が Int の値をオーバーフローして実行時エラーになりますが。 ↩︎

Discussion