为什么是无限类型？（发生检查：不能构造无限类型：a~树a）

Question

data Tree a = Branch a a | Leaf deriving (Show)

construct :: (Integral a) => [a] -> Tree a
construct [] = Leaf
construct (x:[]) = Leaf                -- _____error________
construct (l:r:xs) = if l>r then Branch l (construct $ r:xs) 
                            else Branch (construct $ l:xs) r

* Occurs check: cannot construct the infinite type: a ~ Tree a
* In the second argument of `Branch', namely `(construct $ r : xs)'
  In the expression: Branch l (construct $ r : xs)
  In the expression:
    if l > r then
        Branch l (construct $ r : xs)
    else
        Branch (construct $ l : xs) r
* Relevant bindings include
    xs :: [a] (bound at C:\Stuff\code\New folder (2)\try.hs:69:16)
    r :: a (bound at C:\Stuff\code\New folder (2)\try.hs:69:14)
    l :: a (bound at C:\Stuff\code\New folder (2)\try.hs:69:12)
    construct :: [a] -> Tree a

为什么是无限类型？这个“无限类型”是输入还是输出？

而且，如果我将 更改为construct (x:[]) = Leaf，construct (x:[]) = x则该错误会发生在x. 为什么？

Answer 1

让我们从头开始：

data Tree a = Branch a a | Leaf deriving(Show)

根据定义，这个“树”将包含两个a值（在 a 中Branch）或根本不包含（Leaf）。我不确定为什么将其称为树。看起来这不是你想要做的。也许你想要

data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving(Show)

这是一棵树，a叶子中有值。或者，或者，

data Tree a = Branch a (Tree a) (Tree a) | Leaf deriving(Show)

这是一个a在内部节点中有值的树。

无论如何，让我们解决您的问题：

construct :: (Integral a) => [a] -> Tree a
construct (l:r:xs) = if l>r then Branch l (construct $ r:xs) else ...

在这里，l有类型a。此外，construct $ r:xs产生一个类型的值Tree a。因此，它们有不同的类型：avs Tree a.

然后，您将这两个值传递给Branch它们，根据定义，它们会讲述相同类型的两个值。编译器尝试解决类型相等

 a ~ Tree a

但这立即失败，因为唯一的解决方案是不存在的无限类型

a = Tree (Tree (Tree ...))

最后，要修复您的代码，您需要修改您的树类型，使其实际上是一棵树。之后，您需要根据construct新类型调整代码。

如果我更改为construct (x:[]) = Leaf，construct (x:[]) = x则错误发生在x. 为什么？

因为x有 type a，而constructpromise的签名是a Tree a，因此需要a ~ Tree a与前一种情况一样。