Haskell中的功能依赖

Question

我试图绕过功能依赖,但我自己并没有得到任何结果.在"Monad Transformers Step by Step"一文中,作者给出了这两个类型定义:

class (Monad m) => MonadError e m | m -> e where
    throwError :: e -> m a
    catchError :: m a -> (e -> m a) -> m a

class (Monad m) => MonadReader r m | m -> r where
    ask :: m r
    local :: (r -> r) -> m a -> m a

根据我对在网上发现的一些材料的理解,这意味着类型变量e由确定m.我只是不明白这意味着什么.它是如何确定的？任何人最初都可以用最少的理论解决问题,然后将更重的理论内容联系起来吗？

谢谢

Answer 1

如果您有多参数类型类,默认情况下,类型变量是独立考虑的.所以当类型推断器试图找出哪个实例时

class Foo a b

要选择,它必须确定a并b独立,然后去查看是否存在实例.通过功能依赖,我们可以减少此搜索.当我们做类似的事情

class Foo a b | a -> b

我们说"你看,如果你确定什么a是,那么有一个独特的b,这样Foo a b存在的,所以不要费事去推断b,只是去查找实例和类型检查,认为".这让类型推理器更加有效,并有助于在许多地方进行推理.

例如,这对返回类型多态性特别有用

class Foo a b c where
  bar :: a -> b -> c

现在没有办法推断出来

  bar (bar "foo" 'c') 1

因为我们无法确定c.即使我们只为String和编写了一个实例Char,我们也必须假设某人可能/将会出现并稍后添加另一个实例.如果没有fundeps,我们必须实际指定返回类型,这很烦人.但是我们可以写

class Foo a b c | a b -> c where
  bar :: a -> b -> c

现在很容易看出返回类型bar "foo" 'c'是独特的,因此可推断.

Answer 2

这意味着类型系统始终能够从类型中确定类型(e或r)m.

让我们自己做一个例子:

class KnowsA a b | b -> a where
    known :: b -> a

我们要始终能够确定a从b

data Example1 = Example1 deriving (Show)

instance KnowsA Int Example1 where
    known = const 1 

该型系统知道这个instnace,只要它有一个Example1,它的类型是a会Int.怎么知道的？它不允许我们使用另一种类型的另一个实例.

如果我们补充

instance KnowsA [Char] Example1 where
    known = const "one"

我们收到一个错误:

    Functional dependencies conflict between instance declarations:
      instance KnowsA Int Example1
      instance KnowsA [Char] Example1

但是a如果我们有不同的类型,我们可以添加另一个不同类型的实例b

data Example2 = Example2 deriving (Show)

instance KnowsA [Char] Example2 where
    known = const "two"

main = do
    print . known $ Example1
    print . known $ Example2

这可预测地输出

1
"two"

Answer 3

当Haskell试图解决MonadError e m它时,默认情况下,将两个e和m参数一起搜索,以寻找碰巧有实例的任何一对.如果我们没有e在约束本身之外的类型签名中的任何地方显示,则这尤其困难

unitError :: MonadError e m => m ()
unitError = return ()

功能依赖说,一旦我们解决了m,就只有一个e有效.这让上面的片段编译,因为它向Haskell保证,那里有足够的信息让它具有非模糊类型.

如果没有功能依赖,Haskell会抱怨它unitError含糊不清,因为它可能对任何类型都有效,e而且我们无法知道这种类型是什么 - 信息以某种方式蒸发到空气中.

对于MonadError函数依赖,通常意味着monad本身由错误类型参数化.例如,这是一个实例

instance MonadError e (Either e) where
  thowError = Left
  catchError (Left e)  f = f e
  catchError (Right a) _ = Right a

在哪里e ~ e和m ~ Either e我们看到m确实唯一地确定了一个e有效的单一.

功能依赖性也几乎等同于类型族.类型家庭有时更容易消化.例如,这是一个MonadError类,TypeFamilies样式

{-# LANGUAGE TypeFamilies #-}

class MonadError m where
  type Err m
  throwError :: Err m -> m a
  catchError :: m a -> (Err m -> m a) -> m a

instance MonadError (Either e) where
  type Err (Either e) = e
  throwError = Left
  catchError (Left e) f  = f e
  catchError (Right a) _ = Right a

在这里,Err是一个类型函数,它采用m其特定的错误类型e和概念,如果有任何一个e等于Err m任何等于任何m来自我们对函数的理解.