Zenn
Closed5

型の複雑さについて

Scala
関数型プログラミング
Kugiya JiroKugiya Jiro

モチベーション

  • 型の設計を評価する
    • どちらが「イイ」か客観的に比べたい
      • 良さが数値化されているとよい
Kugiya JiroKugiya Jiro

代数的型システム

あらゆる複合型がそれより小さい直積型や直和型から成立している世界のこと

単純型

型の選択肢が1つしかないような型

直積型(AND型, Product)

異なる複数の型の値を1つの型に集約した型のこと

直和型(OR型, Coproduct)

ある型が複数のいずれかの型であることを示す型のこと

ここでは、直積型を case class、直和型を sealed クラスにエンコードして考える

Kugiya JiroKugiya Jiro

代数的型システムにおける型の複雑さ

取りうる値の数を調べることによって型の複雑さを表現できる

単純型

  • Unit の場合は1
  • Boolean の場合は2
  • Int の場合は 4,294,967,295
  • String の場合は 無限

直積型

  • 直積型の場合、それぞれの値がとりうる値の数を掛ける
    • (Boolean, Boolean) の場合は 4 (2 * 2)
    • (Boolean, Boolean, Boolean) の場合は8 (2 * 2 * 2)

直和型

  • 直和型の場合、それぞれの値がとりうる値の数を足す
    • (Boolean | Boolean | Boolean) の場合は 6 (2 + 2 + 2)
Kugiya JiroKugiya Jiro

全域関数(= total function)の場合

全域関数とは、全ての入力に対して出力が定義されている関数のこと。
（ここでは例外がない関数と考える）
全域関数の複雑さは、その関数のシグネチャを満たしうる入力と出力の組み合わせの数で、出力の複雑さと入力の複雑さの累乗になる

  • Unit => Boolean であれば 2(2^1)
input = Unit
output = true
output = false
  • Boolean => Option[Boolean] であれば 9(3^2)
input = true input = false
output = Some(true) output = Some(true)
output = Some(false) output = Some(false)
output = Some(true) output = Some(false)
output = Some(false) output = Some(true)
output = Some(true) output = None
output = Some(false) output = None
output = None output = Some(true)
output = None output = Some(false)
output = None output = None
  • Option[Boolean] => Option[Boolean] であれば 27 (3^3)

参考

https://users.scala-lang.org/t/complexity-of-a-function/6394

このスクラップは2021/02/11にクローズされました