haskell-jp / beginners #25 at 2024-08-17 13:49:59 +0900

関数従属性について質問させてください

MonadState の定義を見て | m -> s が気になりました。

class (Monad m) => MonadState s m | m -> s where
	get :: m s
	put :: s -> m ()

調べてみたところ、以下のように説明がありました。

"->" の左側にある型によって右側の型が一意に決定される

それ以外にも説明のあるところもあったのですが、納得したといえるほど理解できませんでした。

例)

read "123" :: Int

:: Int がないと "123" がなんの型かわからないよね。

と、いう程度に簡単に理解できるような例はありますか ?
(例えがわかりにくかったら無視してください)

これについてはGHC User Guideの https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/functional_dependencies.html#background-on-functional-dependencies が分かりやすいので例をそのまま引用します。 次:point_down: のような型クラスは FunctionalDependencies を使わないと定義できません:

class Collects e ce where
    empty  :: ce
    insert :: e -> ce -> ce
    member :: e -> ce -> Bool

なぜなら第一に empty メソッドが次 :point_down: のような型になり、

empty :: Collects e ce => ce

empty だけからは e の型が特定できなくなるからです。そのため例えば

instance Collects Word8 ByteString

と、

instance Collects Char ByteString

みたいなインスタンスが複数あると、 empty :: ByteString と書いても要素の型 e が Word8 なのか Char なのか特定できなくなります。

さらに、 insert についても問題があります。`Collects` 型クラスのインスタンスの値に対する次 :point_down: のような関数 f g があったとしましょう:

f x y = insert x . insert y
g     = f True 'a'

これらは次 :point_down: の型に推論されます:

f :: (Collects a c, Collects b c) => a -> b -> c -> c
g :: (Collects Bool c, Collects Char c) => c -> c

ここで Collects が一つの型の値のみを含むコレクション型を対象とした型クラスであった場合、 f は a b という別々の型の値を c に挿入できるようになってしまいます。実際に g では一つの c に対して Bool と Char という別々の型を f に渡していますね。

以上の問題は、`FunctionalDependencies` を有効にして、「 e の型は ce の型が定まれば一意に定まる」という関係を宣言すれば解決できます。

class Collects e ce | ce -> e
  -- ... 以下略 ...

とても丁寧な解説をありがとうございます。

すぐには理解できませんが、教えていただいた内容をもとにじっくりと理解できるように取り組んでみます。

これって実際には

class Collects e ce where
    empty  :: ce

というクラス宣言は The type variable e0 is ambiguous と言われてこのような宣言はできないし、逆に

 class Collects e ce | ce -> e
  -- ... 以下略 ...

とクラス宣言した場合は

instance Collects Word8 ByteString
instance Collects Char ByteString

みたいなインスタンスが複数

宣言に対しては Functional dependencies conflict between instance declarations と言われるので、右側が ByteString のインスタンス宣言は一個しかできませんよね？

はい、両方その通りです。なので、 FunctionalDependencies を「使えばできるようになる」例ではなく「使えばミスが防げる」例です。

これって FunctionDependencies の方が古い時期から使えるんですけど、 TypeFamilies を使えるようになった（のもだいぶ昔ですが、それ以降）からは

class Collects ce where
    type CollectElement ce :: *
    empty  :: ce
    insert :: CollectElement ce -> ce -> ce
    member :: CollectElement ce -> ce -> Bool

instance Collects ByteString where
    type CollectElement ByteString = Char
    略

みたいに書いた方が素直なのかなあ、と思うんですがどうでしょうか

はい、この例に関していえば TypeFamilies を使った方が直感的かとは思います（し、事実そっくりな目的のmono-traversableパッケージでは TypeFamilies を使っています）。
一方、ご存じでしたら恐縮ですが FunctionalDependencies は依存関係を双方向に宣言できたりするので、 TypeFamilies より表現力が高いです。それが理由か、PureScriptでは TypeFamilies はなく代わりに FunctionalDependencies を使っています。

なるほど、双方向性のことについてはすっかり脳内から抜け落ちていました^^;
一対一対応の場合は確かに双方向に使えるのが便利そうですね。