Haskell 对(位 a)推断类型错误的困惑

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 给了我这个错误:

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))

如果我使用 mulGF2n a b g = let (q, r) = divModGF2n (mulGF2 a b) g in r ，也会发生同样的事情。我可以返回元组但不能返回元组的第二个元素，是什么原因？如果我知道类型 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

其中 Haskell Prelude 中提供的函数 asTypeOf 只是为了使 y 和 x 的类型相等。它的定义如下

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

请注意，上面可以有更通用的类型a -> b -> a，但它是用上面的严格类型定义的。这是故意这样做的，以便编译器知道两个参数具有相同的类型。

(执行此操作的另一种常见方法是启用 ScopedTypeVariables 扩展，但对于这个简单的情况来说有点过分了。)