Typecheck奇怪列表清单

Question

我不是一个Haskell专业版。今天，我对今天的类型系统有了一些奇怪的体验。这第二行会导致类型错误。问题是maxdiag (as:bs:cs:ds)位下联：

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds) (len-1)] 

它失败，出现以下错误：

Occurs check: cannot construct the infinite type: a0 = [a0] 
Expected type: [[a0]] 
    Actual type: [a0] 
In the second argument of `(:)', namely `ds' 
In the second argument of `(:)', namely `cs : ds' 

当我改变第二行maxdiag (as:bs:cs:ds:xs)的违规一部分，所以它读取

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds:xs) (len-1)] 

...然后没有错误。同样，如果我将它替换为maxdiag (as:bs:cs:(ds:xs))它会成功。我的问题是

1. 这个错误是什么意思？
2. 它为什么发生？
3. 为什么这两个看似不同的东西解决了它？

Answer 1

要记住的一点是，(:)有型a -> [a] -> [a]，所以它的第一个参数是一个元素，而第二个参数是与元素类型的列表。如果这些元素是它们自己的列表，则这变成[a] -> [[a]] -> [[a]]。

在你的榜样，as，bs，cs和ds都有型[a]，而xs具有类型[[a]]，所以cs:ds时出错，ds:xs是良好的键入。

其原因特定错误消息是，当你试图在同一类型b的两件事情用(:)，只有将工作的方式是，如果b是相同类型的[b]，但是这将是一个无限不允许的类型。

对于另一个问题，(:)运算符是右关联的，所以as:bs:cs:ds:xs与as:(bs:(cs:(ds:xs)))以及as:bs:cs:(ds:xs)相同。

Answer 2

错误：

A.hs:2:63: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    Expected type: [[a0]] 
     Actual type: [a0] 
    In the second argument of `(:)', namely `ds' 
    In the second argument of `(:)', namely `cs : ds' 

意味着你的类型，这是违法的递归限制。即您的类型a必须是a和[a]。

“occurs check”是此时正在执行的部分the type checking algorithm的技术名称。 “发生检查”会阻止构建无限递归类型。

根据我的经验，如果发生类似错误的错误，意味着您混合了(:)和(++)。那就是你有时使用一个值作为列表元素，有时候把它当作列表本身。

在这种情况下，在表达式as:bs:cs:ds中使用(:)。 也许你的意思是这样：

[as,bs,cs,ds]++xs 

请注意，你的代码是非常复杂的 - 它使许多关于列表中的极不可能在所有时间是真实的元素的数量和形状的假设。我会非常害怕这段代码。这将是更加安全：

• 使用模式匹配，以排除其他情况下（例如空列表，缺少的元素）
• 更换索引（!!）与模式匹配。

并认真思考如何简化算法。