Haskell中的函数依赖关系 [英] Functional dependencies in Haskell

问题描述

我试图围绕函数依赖关系来解决问题，但我自己并没有得到任何帮助。在Monad Transformers Step by Step一文中，作者给出了这两个类型定义：

  class（Monad m）=> ; MonadError e m | m  - > e其中
 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  - > ma 
  

从我对一些我在网上找到的资料的理解中，这意味着类型变量 e 由 m 确定。我只是不明白这意味着什么。它是如何确定的？任何人都可以先用最少的理论说明一些事情，然后把更重的理论联系起来？

谢谢

解决方案

当你有一个多参数类型类型时，默认情况下，类型变量被独立地考虑。所以当类型推理器试图找出哪个实例是

  class Foo ab 
  

选择，它必须确定 a 和 b >，然后去查看实例是否存在。有了函数依赖关系，我们可以减少搜索。当我们做一些像

  class Foo a b | a  - > b 
  

我们在说看，如果您确定一个是，那么存在一个唯一的 b ，因此存在 Foo ab 不要试图推断 b ，只要查看实例并查看。这让类型推理更加有效，并有助于推理数字

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

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

现在无法推断

 
 
 
 
 
 
 
 
 
 $因为我们无法确定 c 。即使我们只为字符串和 Char 写了一个实例，我们也必须假设有人可能会来/稍后添加另一个实例。没有fundeps我们不得不实际指定返回类型，这很烦人。但是我们可以写成：
 
 
  class Foo a b c | a b  - > c其中
 bar :: a  - > b  - > c 
  
现在很容易看到 barfoo 'c'是唯一的，因此可以推断。
 
I'm trying to wrap my head around functional dependencies, but I am not getting anywhere on my own.  In the paper "Monad Transformers Step by Step", the author gives these two typeclasses definitions:
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
From my understanding of some of the material I found online, it means that the type variable e is determined by m.  I just don't understand what that means.  How is it determined?  Can anyone shed some light with minimal theory at first, and then link the more heavy theory stuff?

Thanks
解决方案
When you have a multiparameter typeclass, by default, the type variables are considered independently. So when the type inferencer is trying to figure out which instance of
class Foo a b
to choose, it has to determine a and b independently, then go look check to see if the instance exists. With functional dependencies, we can cut this search down. When we do something like
class Foo a b | a -> b
We're saying "Look, if you determine what a is, then there is a unique b so that Foo a b exists so don't bother trying to infer b, just go look up the instance and typecheck that". This let's the type inferencer by much more effective and helps inference in a number of places.

This is particularly helpful with return type polymorphism, for example
class Foo a b c where
  bar :: a -> b -> c
Now there's no way to infer
  bar (bar "foo" 'c') 1
Because we have no way of determining c. Even if we only wrote one instance for String and Char, we have to assume that someone might/will come along and add another instance later on. Without fundeps we'd have to actually specify the return type, which is annoying. However we could write
class Foo a b c | a b -> c where
  bar :: a -> b -> c
And now it's easy to see that the return type of bar "foo" 'c' is unique and thus inferable.

                        
这篇关于Haskell中的函数依赖关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！