Haskell 错误；发生检查：无法构造无限类型：t ~ [t]

Question

我昨天问了几个问题，越来越多的问题不断出现在我的代码中。

我有一个名为 sub 的函数。 Sub 接受一个数字并输出一个数字列表，代码如下。

sub 5 =  [1]
sub x =
    do 
        xs <- sub (x - 1)
        (x:xs)

我曾经不得不在最上面一行有 sub 5 = return [1] 的地方，在最下面一行，return (x:xs)。昨天有人回答说把这些去掉，因为它把一个列表放在一个列表中，就像 [[int]] 一样。如果我取出 returns 这会产生一个错误（在问题标题中），我真的无法理解这个问题。

只是想知道是否有人能理解它，

谢谢

Answer 1

让我们重写您必须做的事情，以便更清楚地说明为什么这不会进行类型检查。我们首先将 do 符号脱糖得到

sub :: Int -> [Int]
sub 5 = [1]
sub x = sub (x-1) >>= \xs -> (x:xs)

现在回想一下如何为列表定义 >>=：ys >>= f = concat (map f ys)。这里 f 是 \xs -> (x:xs) 而 ys 是 sub (x-1)，因此我们有：

sub :: Int -> [Int]
sub 5 = [1]
sub x = concat (map (\xs -> (x:xs)) (sub (x-1)))

sub (x-1) 的类型是 [Int]，因此 map 的第一个参数必须是接受 Int 的函数。它不是 - 它需要一个列表！

正如你所说，你曾经有sub 5 = return [1]。回想一下，对于列表 return y = [y]，那么在那种情况下，您的 sub 将具有签名 Int -> [[Int]]。现在上面的 sub (x-1) 将是列表的列表，而 map 的第一个参数应该是一个接受 lists 的函数，事实确实如此。所以事情经过了类型检查。

一条建议：给你的顶级定义显式签名（你想要 sub :: Int -> [Int] 还是 sub :: Int -> [[Int]]？）！它会让你更容易理解正在发生的事情，因为它会迫使你思考你真正想要的是什么。

Answer 2

我将尝试扩展错误的含义。

让 desugar 做符号 (details):

sub 5 =  [1]
sub x =
        sub (x - 1) >>= \xs ->
        (x:xs)

>>= 运算符具有下一个类型（参见 here）：

(>>=) :: Monad m => m a -> (a -> m b) -> m b

它的第一个参数 sub (x - 1) 的类型为 [Int]，因此我们可以将类型变量 m 实例化为 [] 并将 a 实例化为 Int:

(>>=) :: [Int] -> (Int -> [b]) -> [b]

(注意[a]是列表类型的特殊语法，可以读成[] a)

所以第二个参数 \xs -> (x:xs) 的类型应该是 Int -> [b]。现在应该清楚 xs 的类型是 Int，而不是您所期望的 [Int]。

现在让我们考虑 :。它的类型是 c -> [c] -> [c]。让我们写下所有约束：

(:)     :: c -> [c] -> [c]
x       :: Int
xs      :: Int
x : xs  :: [Int]

他们不能同时满足，因为他们要求 c 和 [c] 都是 Int.

Haskell 错误；发生检查：无法构造无限类型：t ~ [t]

Haskell Error; Occurs check: cannot construct the infinite type: t ~ [t]

haskell

ghci