为什么这个Haskell代码产生"无限类型"错误？

Question

我是Haskell的新手,面对一个我无法理解的"无法构造无限类型"的错误.

事实上,除此之外,我还没有找到这个错误甚至意味着什么的好解释,所以如果你能超越我的基本问题并解释"无限类型"错误,我真的很感激.

这是代码:

intersperse :: a -> [[a]] -> [a]

-- intersperse '*' ["foo","bar","baz","quux"] 
--  should produce the following:
--  "foo*bar*baz*quux"

-- intersperse -99 [ [1,2,3],[4,5,6],[7,8,9]]
--  should produce the following:
--  [1,2,3,-99,4,5,6,-99,7,8,9]

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:y:xs) = x:s:y:intersperse s xs

这是尝试将其加载到解释器中的错误:

Prelude> :load ./chapter.3.ending.real.world.haskell.exercises.hs
[1 of 1] Compiling Main (chapter.3.ending.real.world.haskell.exercises.hs, interpreted )

chapter.3.ending.real.world.haskell.exercises.hs:147:0:
Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `intersperse'
Failed, modules loaded: none.

谢谢.

-

这里有一些更正了代码和处理Haskell中"无限类型"错误的一般准则:

更正了代码

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) =  x ++ s:intersperse s xs 

问题是什么:

我的类型签名表明散布的第二个参数是列表.因此,当我模式匹配"s(x:y:xs)"时,x和y成为列表.然而,我将x和y视为元素,而不是列表.

处理"无限类型"错误的指南:

大多数情况下,当你收到这个错误时,你已经忘记了你正在处理的各种变量的类型,并且你试图使用一个变量,好像它是一些其他类型的变量.仔细查看所有类型与您使用它的方式类型,这通常可以发现问题.

Answer 1

问题出在最后一个子句中,您将x和y视为元素,而它们是列表.这将有效:

intersperse _ [] = []
intersperse _ [x] = x 
intersperse s (x:y:xs) = x ++ [s] ++ y ++ intersperse s xs

发生无限类型错误是因为:运算符具有类型a - > [a] - > [a],而您将其视为[a] - > a - > [a],这意味着必须使用[a]标识a,这意味着a是一个无限嵌套的列表.这是不允许的(而不是你的意思,无论如何).

编辑:上面的代码中还有另一个错误.它应该是:

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) = x ++ [s] ++ intersperse s xs

Answer 2

通常添加显式类型定义可以使编译器的类型错误消息更有意义。但是在这种情况下，显式类型会使编译器的错误消息变得更糟。

看看当我让 ghc 猜测穿插类型时会发生什么：

Occurs check: cannot construct the infinite type: a = [a]
  Expected type: [a] -> [[a]] -> [[a]]
  Inferred type: [a] -> [[a]] -> [a]
In the second argument of `(:)', namely `intersperse s xs'
In the second argument of `(:)', namely `y : intersperse s xs'

这清楚地指向了代码中的错误。使用这种技术，您不必像其他人建议的那样盯着所有东西并仔细考虑类型。