Haskell中兩個相似的函數如何有不同的多態類型？

Question

對於Haskell來說，我很新穎，所以如果我錯過了關鍵概念，請指出。

假設我們有這兩個功能：

fact n 
    | n == 0 = 1 
    | n > 0 = n * (fact (n - 1)) 

的多態類型爲fact是(Eq t, Num t) => t -> t因爲n在if條件使用，n必須是有效的類型做了==檢查。爲此t必須是Number和t可以類約束內是任何類型的Eq t

fib n 
    | n == 1 = 1 
    | n == 2 = 1 
    | n > 2 = fib (n - 1) + fib (n - 2) 

那麼，爲什麼是多態型的fib是(Eq a, Num a, Num t) => a -> t？

我不明白，請幫忙。

Answer 1

haskell總是旨在推導出大多數通用類型簽名。

現在爲fact，我們知道型輸出的，應該是相同的輸入類型：

fact n | n == 0 = 1 
     | n > 0 = n * (fact (n - 1)) 

這是由於最後一行。我們使用n * (fact (n-1))。所以我們使用乘法(*) :: a -> a -> a。乘法因此需要兩個相同類型的成員並返回該類型的成員。由於我們乘以n，並且輸入了n，所以輸出與輸入類型相同。由於我們使用n == 0，因此我們知道(==) :: Eq a => a -> a -> Bool，這意味着該輸入類型應具有Eq a =>，此外還有0 :: Num a => a。所以最終的類型是fact :: (Num a, Eq a) => a -> a。

現在爲fib，我們看到：

fib n | n == 1 = 1 
     | n == 2 = 1 
     | n > 2 = fib (n - 1) + fib (n - 2) 

現在我們知道，n，類型約束再次Eq a, Num a，因爲我們使用n == 1和(==) :: Eq a => a -> a -> Bool和1 :: Num a => a。但輸入n從不直接用於輸出。實際上，最後一行有fib (n-1) + fib (n-2)，但這裏的我們使用n-1和n-2作爲新呼叫的輸入。這意味着我們可以安全地認識到輸入類型和輸出類型獨立運作。輸出類型，仍然有一個類型約束：Num t：這是因爲我們返回1爲前兩種情況，並且1 :: Num t => t，我們還返回加兩個輸出：fib (n-1) + fib (n-2)，所以再次(+) :: Num t => t -> t -> t。

Answer 2

不同的是，在fact，你在一個算術表達式，構成了最終的結果直接使用參數：

fact n | ... = n * ... 

督察，如果你寫出來的擴展算術表達式，n出現在它：

fact 3 ≡ n * (n-1) * (n-2) * 1 

這可修復參數必須具有相同類型的結果，因爲

(*) :: Num n => n -> n -> n 

並非如此在fib：這裏的實際結果只是由文字和sub-結果。 IOW，擴大表情看起來像

fib 3 ≡ (1 + 1) + 1 

沒有n在這裏，所以爭論和結果需要之間沒有統一。

當然，在這兩種情況下，您還使用n來決定這個算術表達式的外觀，但是因爲您剛剛使用了文字的相等比較，而文字的類型並未連接到最終結果。

請注意，您也可以提供fib類型預處理簽名：(Eq a, Num a, Num t) => a -> t嚴格比(Eq t, Num t) => t -> t更一般。相反，你可以通過一個轉換功能之後它使一個fact不需要輸入和輸出是相同類型，：

fact' :: (Eq a, Integral a, Num t) => a -> t 
fact' = fromIntegral . fact 

這沒有很大的意義，但因爲Integer幾乎是唯一可以在fact中可靠使​​用的類型，但要達到上述版本，您需要從Integer開始。因此，如果有的話，你應該做到以下幾點：

fact'' :: (Eq t, Integral a, Num t) => a -> t 
fact'' = fact . fromIntegral 

這可以被也被用來作爲Int -> Integer，這是有點明智的。

我會推薦雖然只保留簽名(Eq t, Num t) => t -> t雖然，並只在實際需要添加轉換操作。或者真的，我推薦根本不使用fact - 這是一個非常昂貴的功能，在實踐中幾乎沒有什麼實際用處;大多數應用程序天真地結束了一個階乘，實際上只需要類似binomial coefficients，並且這些應用程序可以在沒有階乘的情況下更高效地實現。