2014-03-06 29 views
6

如何确定q2和q3的类型?当我输入模块时,模块给了我类型,但是手动执行此操作的可靠方法是什么?请帮忙。谢谢。如何找到haskell定义的一般类型?

q2 x y z w = w (x y) (z y) 

Type is: q2 :: (a -> b) -> a -> (a -> c) -> (b -> c -> d) -> d 

q3 f g x y = (f.g) x == y 

Type is: q3 :: Eq a => (b -> a) -> (c -> b) -> c -> a -> Bool 
+4

@bheklilr他在问怎么做*手工* – chamini2

+1

下面是一个很好的解释(如果有点理论上)它如何工作的链接,一个完整的例子(由第一个人之一实现它在一个真正的编译器不会少)http://web.cecs.pdx.edu/~antoy/Courses/TPFLP/lectures/TYPE/BasicTypechecking.pdf 编辑:和更温和的介绍这里的http:/ /screencasts.chariotsolutions.com/uncovering-the-unknown-principles-of-type-in​​ference-http://screencasts.chariotsolutions.com/uncovering-the-unknown-principles-of-type-in​​ference-http://screencasts .chariotsolutions.com /揭露最未知的原则-的型推理 - – Wes

+2

@ chamini2对不起“布特说,我完全错过了问题的一部分。 – bheklilr

回答

5

井只是分析情理之中的事情:

首先,我们必须

q2 x y z w = w (x y) (z y) 

让我们打破它,从只盯着q2 x y z w我们有,它需要4个参数,以及返回类型太:

q2 :: a -> b -> c -> d -> e 

现在我们来看看每个这些,我们有Ëw (x y) (z y),让我们把它分解成小片:

  • (x y):我们正在使用x作为函数和y作为所述函数的参数,所以x有一个类型x :: b -> f。所以q2现在看起来是这样的:

    q2 :: (b -> f) -> b -> c -> d -> e 
    
  • (z y):具有相同风格所以我们可以说的,我们大约x说,但我们不知道是否xz返还相同种类,所以z看起来像这样z :: b -> g。制作q2这个样子的:

    q2 :: (b -> f) -> b -> (b -> g) -> d -> e 
    

    注:(b -> f)(b -> g)返回不同类型的,因为没有迹象显示(至少到现在为止)他们返还相同种类。

  • w (x y) (z y):这里我们使用w作为函数,以作为参数(x y)(z y),所以现在w有一个类型w :: f -> g -> h。制作q2

    q2 :: (b -> f) -> b -> (b -> g) -> (f -> g -> h) -> e 
    

    注:w需要的返回类型xz的参数。

  • q2 x y z w = w (x y) (z y):我们可以看到,在这个函数的最后一件事是用w作为一个函数,那么什么w的回报是什么q2应该返回,所以最后q2看起来是这样的:

    q2 :: (b -> f) -> b -> (b -> g) -> (f -> g -> h) -> h 
    

希望它有帮助,你应该自己练习q3。让我知道你是否有困难。

11

类型信息从现有构造流向新构造。让我们来看看你的例子:

q2 x y z w = w (x y) (z y) 

它可能不是很明显,但这个功能已经调用某些类型的哈斯克尔元。特别是,它使用了具有类型

($) :: (a -> b) -> a -> b 

功能应用。事实上,我们可以使用($)语法就这样让我们的使用的功能应用更加明确。

q2 x y z w = (w $ x $ y) $ z $ y 

或者,我们可以重新制定它,比方说,使用Javascript式的语法来看看应用程序更清晰地再次

q2(x)(y)(z)(w) = w(x(y))(z(y)) 

在任何情况下,应该明确的是,有发生4级功能的应用。从这些我们将产生的信息,给我们的主要类型q2


扩展类型推断的主要方法是“统一”,这是说,如果我们知道一个东西有类型AB那么我们必须能够转化ABC,第三类这与AB一致。它甚至可以是AB

| A  | B  | C  | 
|--------|--------|--------| 
| String | a  | String | 
| Int | String | <fail> | 
| a  | b  | c  | (where we suppose a == b == c) 
| a -> b | c -> d | e -> f | (where we suppose a == c == e 
|  |  |  |    and b == d == f) 

正如你可以看到两个统一的进一步的特征:(1)如果和(2)它有时会导致我们假设类型变量之间的平等它可能会失败。一般来说,这就是推论的过程:我们为所有我们不知道的事物分配一个新的类型变量,然后尝试统一所有的部分。一路上我们可能会失败(因此我们说类型检查失败了),或者我们会收集大量的平等信息,告诉我们我们已经引入了大量的冗余类型变量。然后,我们通过消除所有冗余变量来总结信息,直到我们不再需要说明我们的均等。

id  :: a -> a 
    3 :: Num a => a 
    3 :: Num b => b  -- make the variable fresh/not conflict with `a` 
id 3 :: Num c => c (supposing a == b == c) 
id 3 :: Num a => a (supposing nothing, we've forgotten about b and c) 

因此,我们可以应用该方法q2。手工操作有点冗长,但易于手动完成。我们正在寻找价值q2的类型。我们知道q2需要4个参数,返回的东西,所以我们可以通过统一的x的类型,z构建类型立即

q2 :: a -> b -> c -> d -> e 

我们知道,和w同类型应用($)该类型ac绝与功能

q2 :: (f -> g) -> b -> (h -> i) -> d -> e 

和它们的输入参数必须具有兼容的类型与他们的参数值兼容y :: b

q2 :: (b -> g) -> b -> (b -> i) -> d -> e 

最后,我们可以检查w看到,它的一个函数,它接受的x y类型的参数,返回另一个函数,它接受的z y类型的参数,返回的东西

q2 :: (b -> g) -> b -> (b -> i) -> (g -> (i -> j)) -> e 

这由(->)右关联性,我们通常写为

q2 :: (b -> g) -> b -> (b -> i) -> (g -> i -> j) -> e 

最后,我们知道,的返回类型是全功能

q2 :: (b -> g) -> b -> (b -> i) -> (g -> i -> j) -> j 

其中,达重命名,是q2最后,最一般类型的返回类型。


欲了解更多信息,调查Hindley-Milner and Algorithm W。我松散覆盖了大部分的细节,但也有少数剩余的想法,他们都可以仔细更加检查。

1

一篇很好的论文,可以深入了解Haskell的类型系统,也是“在Haskell中键入Haskell”,您可以在其中真实地看到Hindley-Milner类型推断如何由程序完成。 http://web.cecs.pdx.edu/~mpj/thih/

由于Haskell是强类型化的,可以随时推断所有类型的所有功能,从非限制性类型的变量的假设,这可能会受到限制,以通过上下文的更具体的类型或类型的类开始(其他功能需要特定类型)。

J.亚伯拉罕解释得很好。 :)