发生检查：无法构造无限类型：t〜[t]

Question

我开始学习Haskell。我试图运行此代码

-- Helpers.hs 
module Helpers 
where 

lst1 +++ lst2 = if null lst1 
      then lst2 
      else (head lst1) : (tail lst1 +++ lst2) 


reverse2 lst = if null lst 
      then [] 
      else reverse2 (tail lst) : (head lst) 

-- Main.hs 
import Helpers 

main :: IO() 
main = putStrLn . reverse2 [2, 8, 7] 

我收到此错误：

D:\Haskell\project>cabal configure 
Resolving dependencies... 
Configuring one-0.1.0.0... 

D:\Haskell\project>cabal build 
Building one-0.1.0.0... 
Preprocessing executable 'one' for one-0.1.0.0... 
[1 of 2] Compiling Helpers   (src\Utils\Helpers.hs, dist\build\one\one-t 
mp\Helpers.o) 

src\Utils\Helpers.hs:11:21: 
    Occurs check: cannot construct the infinite type: t ~ [t] 
    Relevant bindings include 
     lst :: [[t]] (bound at src\Utils\Helpers.hs:9:10) 
     reverse2 :: [[t]] -> [t] (bound at src\Utils\Helpers.hs:9:1) 
    In the first argument of `(:)', namely `reverse2 (tail lst)' 
    In the expression: reverse2 (tail lst) : (head lst) 

我怎样才能解决这个问题？

Answer 1

所以眼前的问题是，你传递错误类型的参数到:运算符，并且haskell试图使它们成为正确的类型，并且使它们成为正确类型的努力导致了模糊的错误消息。

作为一般策略，当奇怪的错误消息像这样出现时，我开始将类型签名应用于它所抱怨的事物，这样haskell就不会试图推断远离我想要的类型签名。

这样做，以你的代码，我想加入这reverse2开始：

reverse2 :: [t] -> [t] 
reverse2 lst = if null lst 
      then [] 
      else reverse2 (tail lst) : (head lst) 

这改变了错误消息：

Couldn't match expected type ‘t’ with actual type ‘[t]’ 
     ‘t’ is a rigid type variable bound by 
      the type signature for reverse2 :: [t] -> [t] 
      at /tmp/flycheck-stackov.hs:6:13 
    Relevant bindings include 
     lst :: [t] (bound at /tmp/flycheck-stackov.hs:7:10) 
     reverse2 :: [t] -> [t] (bound at /tmp/flycheck-stackov.hs:7:1) 
    In the first argument of ‘(:)’, namely ‘reverse2 (tail lst)’ 
    In the expression: reverse2 (tail lst) : (head lst) 

好了，现在它说：“我预计类型t，但在查看:的第一个参数时得到了类型[t]“。

事实上，如果我们问ghci的:的类型是什么，我们可以看到：

Prelude> :t (:) 
(:) :: a -> [a] -> [a] 

于是左手参数:需求为单个项目，而右边的参数列表。您正在使用左侧的列表，右侧使用单个项目。

要连接你想要的方式，因为对方回答说，你应该使用++：你想说putStrLn $ reverse2 [2, 8, 7]而不是

reverse2 :: [t] -> [t] 
reverse2 lst = if null lst 
      then [] 
      else reverse2 (tail lst) ++ [head lst] 

（另外，你在你的日常main有一个类型的错误putStrLn . reverse2 [2, 8, 7]）

Answer 2

reverse2 (tail lst)是[a]类型，而head lst是a类型。同时，:运营商的类型为a -> [a] -> [a]。当您尝试执行reverse2 (tail lst) : (head lst)时，Haskell认为head lst是一个列表，其元素与reverse2 (tail lst)相同 - 即head lst :: [[a]]。然而，head lst也必须是与reverse2 (tail lst)的元素相同的类型，这意味着reverse2 (tail lst) :: [[[a]]]，但然后head lst必须是[[[[a]]]]，然后reverse2 (tail lst)必须是[[[[[a]]]]]，并且我认为您可以看到这是怎么回事。

发生此问题是因为您错误地使用了:。如果要将元素附加到列表中，最简单的方法是reverse2 (tail lst) ++ [head lst]。

Answer 3

就像一张纸条上扩大写道，如果你明确地类的东西，你可以得到一个更实用的错误消息是什么jwodder：

Prelude> let reverse2 :: [a] -> [a]; reverse2 lst = if null lst then [] else (reverse2 (tail lst)) : (head lst) 

<interactive>:6:70: 
    Couldn't match expected type ‘a’ with actual type ‘[a]’ 
     ‘a’ is a rigid type variable bound by 
      the type signature for reverse2 :: [a] -> [a] at <interactive>:6:17 
    Relevant bindings include 
     lst :: [a] (bound at <interactive>:6:38) 
     reverse2 :: [a] -> [a] (bound at <interactive>:6:29) 
    In the first argument of ‘(:)’, namely ‘(reverse2 (tail lst))’ 
    In the expression: (reverse2 (tail lst)) : (head lst) 

Answer 4

你应该能够解决它：

reverse2 lst = if null lst 
    then [] 
    else reverse2 (tail lst) ++ [head lst] 

@jwodder已经解释更多的理论原因，这是行不通的。

请注意，上面的实现效率非常低，因为++完全遍历其第一个参数并在之后进行串联。

一个更复杂的方法是以下

reverse3 lst = 
    let aux lst acc = if null lst then acc else aux (tail lst) (head lst : acc) 
    in aux lst [] 

它往往是有益明确标注类型（即你写reverse2 :: [a] -> [a]。