🔢

カーディナリティから考える関数の複雑さ

に公開
関数型
tech

概要

関数の複雑さを測る指標としてカーディナリティ(Cardinality) という概念が便利という内容です。
この単語は、Matt ParsonsさんのKeep your types small...というブログの中で紹介されています。

本題

カーディナリティ

カーディナリティとは型に属する値の総数のことです。
例：
• Boolean のカーディナリティ：2 {true, false}
• Unit のカーディナリティ：1 {()}
• Option[A] のカーディナリティ：1 + |A|
• Either[A, B] のカーディナリティ：|A| + |B|
• (A, B)（タプル）のカーディナリティ：|A| × |B|

関数の複雑さ

関数fが次のように定義されているとします。

f :: A -> B

このとき、定義可能な関数の数は次のように表されます。

|B|^{|A|}

これは、A のそれぞれの値に対して B のどの値を対応させるかを選ぶためです。
この値をここでは、関数の複雑さと呼ぶことにします。

関数の複雑さが低ければ、必要なテストが少なくて済みます。また、関数合成をすればするほど恩恵が大きくなります。

戻り値を制限するのと引数を制限するのではどちらの方が良いか

safeIsPrime の例

戻り値を制限した場合：

safeIsPrime1 :: PositiveInt -> Bool

ここで PositiveInt は 1 以上の整数のみを許す型です。

  • PositiveInt のカーディナリティは (|Int|- 1) / 2
  • 戻り値 Bool のカーディナリティは 2

よって、関数の複雑さは：

2^{(|Int|- 1) / 2}

引数を制限しないで、戻り値で失敗を表す場合：

safeIsPrime2 :: Int -> Maybe Bool
  • 引数 Int のカーディナリティは |Int|
  • 戻り値 Maybe Bool のカーディナリティは 1 + 2 = 3

よって、関数の複雑さは：

3^{|Int|}

比較すると：
safeIsPrime1 の方が複雑さが小さいです。
よって、カーディナリティに注目すると safeIsPrime1 の方が良いということになります。

safeMax の例

戻り値を制限した場合：

safeMax1 :: NonEmptyList Int -> Int

ここで NonEmptyList Int は空でないリストのみを許す型です。

  • NonEmptyList Int のカーディナリティは |[Int] - 1|
  • 戻り値 Int のカーディナリティは |Int|

よって、関数の複雑さは：

|Int|^{|[Int] - 1|}

引数を制限しないで、戻り値で失敗を表す場合：

safeMax2 :: [Int] -> Maybe Int
  • 引数 [Int] のカーディナリティは |[Int]|
  • 戻り値 Maybe Int のカーディナリティは |Int| + 1

よって、関数の複雑さは：

{(|Int| + 1)}^{|[Int]|}

比較すると：
両者の複雑さは数学的には無限ですが、safeMax1 の方がパターン数が少ないです。
そのため、実用上の複雑さや安全性、テスト容易性の観点で safeMax1 の方が優れていると言えます。

まとめ

カーディナリティの観点から見ると
• 戻り値に失敗を含めると、戻り値のカーディナリティが増える → 関数の複雑さが増す
• 引数側で不正な入力をそもそも表現できなくする → 関数の複雑さが下がる
となります。
よって、関数の安全性やテスト容易性、合成のしやすさを考えると、戻り値で制御するよりも、引数を制限する方が望ましいケースが多いといえます。
カーディナリティという指標は、こうした選択の一つの指標になります。

参考文献

より安全で単純な関数定義 by がくぞ
Keep your types small...

Discussion