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,唯一可行的方法是if 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].

" 发生检查 "是此时正在执行的类型检查算法部分的技术名称."发生检查"阻止构建无限递归类型.

根据我的经验,失败发生检查与列表般的错误意味着你正在混淆(:)和(++).那就是你有时使用一个值作为列表元素,有时候作为一个列表本身.

在这种情况下,它是(:)在表达式中的使用as:bs:cs:ds.可能你的意思是:

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

请注意,您的代码非常复杂 - 它对列表中元素的数量和形状进行了大量假设,这些假设在任何时候都不太可能是真实的.我会非常害怕这段代码.它会更安全:

• 使用模式匹配来排除其他情况(例如空列表,缺少元素)
• 用模式匹配替换索引(!!).

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