haskell - 为什么它是无限类型的？ (发生检查 : cannot construct the infinite type: a ~ Tree 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 值(在 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 的值。因此它们有不同的类型:a 与 Tree a。

然后您获取这两个值并将它们传递给 Branch，根据定义，它代表两个相同类型的值。编译器尝试解决类型相等问题

 a ~ Tree a

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

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

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

---

If I change the construct (x:[]) = Leaf to construct (x:[]) = x then the error occurs in that x. Why?

因为 x 的类型是 a，而 construct 的签名 promise 一个 Tree a，因此需要 a ~ Tree a 和前面的例子一样。