haskell - 为什么应用于具有相同函数的不同输入的多态函数的类型推断失败

Question

我正在为 C++ 的一个子集制作一个解释器。解释器是用 Haskell 编写的。

我eval的表达式函数返回一个新环境和一个值。我将这些值编码为一种名为Val. 最小的例子：

data Val = I Integer | D Double

为了评估算术表达式，我想创建一个通用函数，该函数将多态函数应用(+)到构造函数(*)中包装的数字上。Val

我想要这样的功能：

-- calculate :: Num a => (a -> a -> a) -> Val -> Val -> Val
calculate f (I i1) (I i2) = I (f i1 i2)
calculate f (D d1) (D d2) = D (f d1 d2)

这给出了以下错误：

tmp/example.hs:4:32: error:
    • Couldn't match expected type ‘Double’ with actual type ‘Integer’
    • In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
      In an equation for ‘calculate’:
          calculate f (D d1) (D d2) = D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                ^^^^^^^

tmp/example.hs:4:34: error:
    • Couldn't match expected type ‘Integer’ with actual type ‘Double’
    • In the first argument of ‘f’, namely ‘d1’
      In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                  ^^

tmp/example.hs:4:37: error:
    • Couldn't match expected type ‘Integer’ with actual type ‘Double’
    • In the second argument of ‘f’, namely ‘d2’
      In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                     ^^

我无法解决这个问题。我有两个问题：

1. 为什么这个程序无法进行类型检查？
2. 我怎样才能calculate正确实施？

我对普遍量化的类型只是模糊熟悉，所以如果这是问题的一部分，请温和地解释。

标签： haskelltypechecking

Answer 1

您已经正确地确定了您需要通用量化。事实上，你已经有了通用量化——你的签名，就像任何多态签名一样，基本上是

{-# LANGUAGE ExplicitForall, UnicodeSyntax #-}
calculate :: ∀ a . Num a => (a -> a -> a) -> Val -> Val -> Val

含义：每当有人想使用此功能时，他们可以选择某种类型以a预先输入。例如，他们可以选择Int，然后该函数将专门用于

calculate :: (Int -> Int -> Int) -> Val -> Val -> Val

然后在运行时使用。

但这对您没有用，因为您将需要将此函数用于不同的数字类型。没有一个专业可以涵盖所有这些。

解决方案：延迟选择类型。这是通过将通用量器∀（您也可以编写它forall）放在签名的组合函数部分中来完成的：

{-# LANGUAGE Rank2Types #-}
calculate :: (∀ a . Num a => a -> a -> a) -> Val -> Val -> Val

这将进行类型检查。它确实需要-XRank2Types扩展，因为这是一个相当复杂的野兽：现在您不能简单地将多态函数描绘为具有具体单态类型的一系列特化，而是该函数需要准备好在运行时实例化所提供的数据结构中发生的任何类型的函数。

即，它需要向函数传递一个附加参数：一个包含Num类方法的“字典”。GHC 生成的底层实现是这样的：

data NumDict a = NumDict {
        addition :: a -> a -> a
      , subtraction :: a -> a -> a
      , multiplication :: a -> a -> a
      , abs :: a -> a
      ...
      }

calculate' :: (∀ a . NumDict a -> a -> a -> a) -> Val -> Val -> Val
calculate' f (I i1) (I i2) = I (f ndict i1 i2)
 where ndict = NumDict ((+) :: Integer -> Integer -> Integer)
                       ((-) :: Integer -> Integer -> Integer)
                       ...