使用foldr的Haskell類型類

Question

我使用foldr編寫了一個函數，該函數確定列表或字符串的長度。我有點困惑，爲什麼Haskell確定類型爲Num。當然字符串不包括在這個類中？但是Haskell堅持認爲它必須如此，否則這個函數將無法工作。有人可以幫助澄清這是爲什麼嗎？

myLength' :: (Num a) => [a] -> Int 
myLength' xs = foldr (\x acc -> 1 + acc) 0 xs 

Answer 1

我認爲您的類型簽名可能已被您的聲明過於具體。下面是我在GHCI得到：

> :t foldr 
foldr :: (a -> b -> b) -> b -> [a] -> b 

> :t foldr (\x acc -> acc + 1) 
... :: Num b => b -> [a] -> b 

的+是在Num約束從何而來。它僅適用於b類型，因爲acc的類型與b一致。沒有進一步的約束，因爲我們沒有做任何事情x :: a。

> :t foldr (\x acc -> acc + 1) 0 
... :: Num b => [a] -> b 

0容易與Num b => b結合並沒有什麼變化，除了我們放棄一個箭頭。

> :t \xs -> foldr (\x acc -> acc + 1) 0 xs 
... :: Num b => [a] -> b 

我們引入了一個參數xs沒有特定的類型，它很容易與[a]結合。沒有什麼變化。所以，我們最後的類型應該是

myLength :: (Num b) => [a] -> b 
myLength = foldr (\_ acc -> 1 + acc) 0 

這確實對字符串工作。 myLength "hello" => 5等。

如李評價所提到的，foldr的類型在GHC 7.10改變爲Foldable t => (a -> b -> b) -> b -> t a -> b作爲Foldable Traversable in Prelude Proposal，這允許foldr要對許多不同的數據結構，而不是僅僅列出了用於的一部分。在GHC 7.10上，你的函數確實有一個類型推斷myLength :: (Foldable t, Num b) => t a -> b。請注意0​​概括如下[a]。

HOORAY TYPES