Haskell的类型系统是如何产生这个错误的？

Question

在我通过Haskell进行的冒险中，我发现当我对代码中的类型犯了错误时，我很难去分析我做错了什么，编译器在抱怨什么。我认为这是因为在编译器发现错误之前的部分类型推断。

当然，我习惯于那些类型不匹配非常明显的语言。类似于function foo expects an argument of type int, but received string的东西。很明显，这意味着，我传入了一个字符串，但是签名需要一个int。

因此，这里有一些相对简单的代码，它是一个函数，它计算给定系数和幂列表的多项式：

poly :: [Int] -> [Int] -> Double -> Double
poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip a $ b

这会产生以下编译器错误输出：

[1 of 1] Compiling Main             ( solution.hs, solution.o )

solution.hs:11:56: error:
    • Couldn't match type ‘Int’ with ‘Double’
      Expected type: [Double] -> [(Double, Double)]
        Actual type: [Double] -> [(Int, Double)]
    • In the second argument of ‘(.)’, namely ‘zip a’
      In the second argument of ‘(.)’, namely
        ‘map (\ (ai, bi) -> ai * (x ** bi)) . zip a’
      In the expression: sum . map (\ (ai, bi) -> ai * (x ** bi)) . zip a
   |
11 | poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip a $ b
   |                                                        ^^^^^

solution.hs:11:64: error:
    • Couldn't match type ‘Int’ with ‘Double’
      Expected type: [Double]
        Actual type: [Int]
    • In the second argument of ‘($)’, namely ‘b’
      In the expression:
        sum . map (\ (ai, bi) -> ai * (x ** bi)) . zip a $ b
      In an equation for ‘poly’:
          poly a b x = sum . map (\ (ai, bi) -> ai * (x ** bi)) . zip a $ b
   |
11 | poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip a $ b
   |                                                                ^

所以我已经知道这里出了什么问题。a和b是[Int]型的，但我需要它们是[Double]型的。然而，我不明白的是，为什么编译器要说它是什么：

1. 为什么当b在表达式中出现在a之前并且同样错误的时候，它会抱怨它？
2. 在最上面的错误中，预期的类型是[(Double, Double)].酷，说得通。但是为什么实际的类型是[(Int, Double)]呢？如果a和b都是[Int]，那么这两种情况是如何出现的呢？

在这两种情况下，我认为我真正需要的是让我了解类型系统最终是如何生成这些错误的，这样我就能更好地理解为什么错误信息是这样的。

Answer 1

为什么当b在表达式中出现在a之前并且同样错误的时候，它会抱怨它？

...why不是吗？你自己也说过他们都错了。GHC还发现他们都错了。告诉你他们都错了。而且，a并不是真正“在前面”，因为在Haskell中没有真正的“前”和“后”的概念。如果有的话，它是“输入”，而不是“左-右”，然后b (仅在($)下面)是“在”a之前(在zip、(.)和($)下面)。不管怎样，这不重要。

在最上面的错误中，预期的类型是[(Double, Double)].酷，说得通。但是为什么实际的类型是[(Int, Double)]呢？如果a和b都是[Int]，那么这两种情况是如何出现的呢？

sum . map _etc . zip a应该具有[Int] -> Double类型，这是因为类型签名以及它是($)的左侧。钻得更深一点，zip a应该是[Int] -> [(Double, Double)]。它实际上是forall b. [b] -> [(Int, b)]。使用参数类型，我们可以选择设置b ~ Int，从而推断出在需要[Double] -> [(Double, Double)]的地方，zip a实际上是[Int] -> [(Int, Int)] (这是真的)，或者我们可以选择设置b ~ Double (从返回类型)，并决定实际上是zip a :: [Double] -> [(Int, Double)] (这也是真的)。两种方法都有错误。事实上，我认为GHC是以第三种方式进行的，类似于第一种方式，但我将不谈细节。

问题的核心是:在Haskell程序中，如果您知道周围或其中的内容的类型，就有多种方法来确定表达式的类型。在一个类型良好的程序中，所有这些派生都是一致的，而在一个错误类型的程序中，它们通常在多个方面不一致。GHC简单地选择了其中的两个，称之为“预期的”和“实际的”，希望这是有意义的，并抱怨他们不同意。在这里，您发现了第三个派生，它也与“预期”派生发生冲突，但是GHC，无论出于什么原因，都选择不将派生用于“实际类型”。选择要显示哪个派生是不容易的，特别是在Haskell中，在Haskell中，一切都可以影响其他所有事物的类型，尽管它肯定会更好。几年前，GHC的一位领导者在更好的错误信息上做了一些工作，但它似乎有链接的轻微腐烂-Haskell-分析器桥似乎已经从互联网上的链接腐烂。

如果您面临这样的错误，首先，我建议您不要使用_ . _ . ... $ _风格编写。如果你把它写成_ $ _ $ ... $ _，那么遵循我的主要建议就更容易了。我不会在这里改的，但你应该记住这一点。

poly :: [Int] -> [Int] -> Double -> Double
poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip a $ b

你看到了一个错误，现在还不清楚要改变什么。很好，简单地放弃尝试破译象形文字，用_替换RHS的一部分。删除的RHS越多，发现错误的可能性就越大，如果您删除所有这些错误，则将达到95%：

poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . _ $ _
-- personally, I'd nuke the scary-looking map _lambda, too,
-- but I'm also trying to keep this short

GHC会告诉您左边的_是_a -> [(Double, Double)]，右边的是_a。添加zip

poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip _ $ _

您将被告知需要两个[Double]，并且您将意识到使用a和b并不有效，因为a, b :: [Int] (而GHC实际上在错误消息中表示a :: [Int]; b :: [Int]，因为有时不清楚)。然后，您就会知道如何修复它：

poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip (fromIntegral <$> a) $ fromIntegral <$> b

平安无事。

Answer 2

拥有

poly :: [Int] -> [Int] -> Double -> Double
poly a b x = sum . map (\(ai, bi) -> ai * (x ** bi)) . zip a $ b

一方面，

    a ::        [ Int]
zip a :: [t] -> [(Int,t)]
x :: Double
x ** bi :: Double
     bi :: Double
                      t ::    Double
zip a   :: [Double] -> [(Int, Double)]                     derived

但另一方面，

poly a b x          ::                      Double
sum                 ::          [Double] -> Double
    ai * (x ** bi)  ::           Double
   (ai ,       bi)  ::  (Double, Double)
zip a   :: [Double] -> [(Double, Double)]                  expected