2014-03-06 22 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.亞伯拉罕解釋得很好。 :)