哈斯克爾混淆（位的）推斷的錯誤類型

Question

我一些數學函數試驗，並已拿出了以下內容：

import Data.Bits 

mulGF2n a b g = divModGF2n (mulGF2 a b) g 
    where 
    mulGF2 a b 
     | a == zeroBits = zeroBits 
     | otherwise  = xor (if testBit a 0 then b else zeroBits) (mulGF2 (shiftR a 1) (shiftL b 1)) 

divModGF2n a b = go a zeroBits 
    where 
    n  = log2 b 
    log2 a = let x = shiftR a 1 in if x == zeroBits then 0 else 1 + log2 x 
    go a q 
     | r < 0  = (q, a) 
     | otherwise = go (xor a (shiftL b r)) (q .|. bit r) 
     where 
     r = log2 a - n 

他們迦羅華域的計算，但他們做了什麼都沒有重要。注意我省略了類型簽名。

GHCI告訴我下面講的推斷類型：

*Main> :t divModGF2n 
divModGF2n :: (Bits t1, Bits t) => t -> t -> (t1, t) 

*Main> :t mulGF2n 
mulGF2n :: (Bits a, Bits t1, Bits t) => a -> t -> t -> (t1, t) 

到目前爲止好。我嘗試修改mulGF2n函數，以便不返回類型爲(t1, t)的元組，而是僅返回類型爲t的第二個元素。

mulGF2n a b g = divModGF2n (mulGF2 a b) g 

到：我從修改函數的第一行

mulGF2n a b g = snd $ divModGF2n (mulGF2 a b) g 

現在，GHCI給了我這個錯誤：如果我改用mulGF2n a b g = let (q, r) = divModGF2n (mulGF2 a b) g in r

Could not deduce (Bits a0) arising from a use of ‘divModGF2n’ 
from the context (Bits a, Bits b) 
    bound by the inferred type of 
      mulGF2n :: (Bits a, Bits b) => a -> b -> b -> b 
    at polydiv.hs:(12,1)-(16,100) 
The type variable ‘a0’ is ambiguous 
Note: there are several potential instances: 
    instance Bits Bool -- Defined in ‘Data.Bits’ 
    instance Bits Int -- Defined in ‘Data.Bits’ 
    instance Bits Integer -- Defined in ‘Data.Bits’ 
    ...plus one other 
In the first argument of ‘snd’, namely 
    ‘(divModGF2n (mulGF2 a b) g)’ 
In the expression: snd (divModGF2n (mulGF2 a b) g) 
In an equation for ‘mulGF2n’: 
    mulGF2n a b g 
     = snd (divModGF2n (mulGF2 a b) g) 
     where 
      mulGF2 a b 
      | a == zeroBits = zeroBits 
      | otherwise 
      = xor 
       (if testBit a 0 then b else zeroBits) 
       (mulGF2 (shiftR a 1) (shiftL b 1)) 

同樣的事情發生。什麼原因可以返回元組而不是元組的第二個元素？如果我知道錯誤中提及的類型a0，但它只會抱怨類型，但不會告訴我它指的是哪一種。

Answer 1

我會用一個更簡單的例子來解釋這個問題。

考慮一下：

class C a where def :: (Int, a) 

f :: (Eq a, C a) => Int -> (a, Bool) 
f x = let (y,z) = def in (z, x==y) 

上述功能返回兩個值，a類型（在C類）中的一個，和一個Bool。請注意，第二個結果實際上取決於a的實際情況。要知道爲什麼，可以考慮：

> instance C Char where def = (0, 'a') 
> instance C() where def = (1,()) 
> f 0 :: (Char,Bool) 
('a', True) 
> f 0 :: ((), Bool) 
((), False) 

現在，考慮一下：

> snd (f 0) :: Bool 

這不可能是正確的：它應該是True或False取決於什麼a用於調用f。編譯器無法推斷這個a應該是什麼，所以它在類型檢查過程中拒絕上述程序。

更詳細地，它生成以下類型：

f :: (Eq a, C a) => Int -> (a, Bool) -- OK 
f 0 :: (Eq a, C a) => (a, Bool)  -- OK 
snd (f 0) :: (Eq a, C a) => Bool  -- NOT OK 

最後一類是無效的，因爲a出現在約束，但是不在下面它們的類型。

如果您確實想要這樣做，您必須手動提供a，例如，

snd (f 0 :: (Char, Bool)) :: Bool  -- OK 

在代碼中，你有

mulGF2n :: (Bits a, Bits t1, Bits t) => a -> t -> t -> (t1, t) 

，如果你伸出的第二部分你建立一個功能

g :: (Bits a, Bits t1, Bits t) => a -> t -> t -> t 
g a b c = snd $ mulGF2n a b c 

其中t1只出現在約束，所以類型是無效的。如果你想選擇t1=t，那麼你必須告知您所選擇的編譯器：

g :: (Bits a, Bits t) => a -> t -> t -> t 
g a b c = y `asTypeOf` x 
    where (x,y) = mulGF2n a b c 

其中函數asTypeOf在Haskell的前奏剛剛製作的各類y和x平等的目的而提供。它的定義是一個簡單以下

asTypeOf :: a -> a -> a 
asTypeOf x y = x 

注意上面可能有更多的普通型a -> b -> a，但它與上述stricted類型定義。這是有目的地完成的，以便通知編譯器兩個參數具有相同的類型。

（另一種常見的方式做，這是使ScopedTypeVariables擴展，但它是這個簡單的例子有點矯枉過正。）

Answer 2

在mulGF2n的t1類型的變量是完全無關的它被賦予的參數。因此，GHC不知道如何爲它選擇一個類型，它仍然不明確。

這裏是同一個問題的一個小例子：

default() 

example :: (Num a, Num b) => (a, b) 
example = (1, 2) 

exampleFst :: Num a => a 
exampleFst = fst example 

（需要的default()因爲GHC在如何解決曖昧Num類型的特殊規則，此行讓我們可以關閉這些功能。）

我們得到一個模棱兩可的類型錯誤，因爲GHC不知道如何爲example中的b類型變量選擇一個Num實例。由於它沒有在其他地方使用，所以沒有給出任何幫助確定它應該是什麼類型的線索。我們可以通過限制，排除了這個錯誤是特定類型具有顯式類型簽名：

{-# LANGUAGE ScopedTypeVariables #-} 
exampleFst :: forall a. Num a => a 
exampleFst = fst (example :: (a, a)) 

的ScopedTypeVariables擴展告訴GHC我們希望在第三行的顯式類型簽名a是一樣的在exampleFst的類型簽名中設置了a（啓用此擴展時爲forall）。

類似的方法可以用來解決你的類型錯誤。

Answer 3

要看看發生了什麼，首先我們將log2從divModGF2n中分離出來，並給它一個類型簽名。 log2的結果是任意數字。

log2 :: (Bits a, Num n) => a -> n 
log2 a = let x = shiftR a 1 in if x == zeroBits then 0 else 1 + log2 x 

現在讓我們來看看divModGF2n

divModGF2n a b = go a zeroBits 
    where 
    n  = log2 b 
    go a q 
     | r < 0  = (q, a) 
     | otherwise = go (xor a (shiftL b r)) (q .|. bit r) 
     where 
     r = log2 a - n 

的第二個參數go，q，從來沒有什麼，但本身交互。它開始爲zeroBits :: Bits a => a。它計算從q .|. bit r遞歸步驟。 bit :: Bits a => Int -> a和(.|.) :: Bit a => a -> a -> a。我們無法確定q的類型，除了在返回(q, a)時使用它的方式。這就是爲什麼在divModGF2n的簽名中有一個額外的類型變量t1。

:t divModGF2n 
divModGF2n :: (Bits t1, Bits t) => t -> t -> (t1, t) 

現在讓我們看看如果我們試圖定義一個函數來返回餘數，會發生什麼。

modGF2n :: Bits a => a -> a -> a 
modGF2n a b = let (q, r) = divModGF2n a b 
       in r 

我們得到以下錯誤。

Could not deduce (Bits a0) arising from a use of `divModGF2n' 
from the context (Bits a) 

發生了什麼事是我們只能從它是如何被退回時，使用確定的商的類型divModGF2n。 modGF2n不使用商，所以我們無法確定其類型。編譯器需要這種類型的Bits實例才能使用divModGF2n。這就是我們收到錯誤消息的原因。

作爲程序員，我們可以觀察到divModGF2n的餘數不依賴於商。我們可以通過提供一個具有Bits實例的類型來定義modGF2n，並且它不會影響餘數的計算方式。

{-# LANGUAGE ScopedTypeVariables #-} 

modGF2n :: Bits a => a -> a -> a 
modGF2n a b = let (q :: Bool,r) = divModGF2n a b 
       in r