1 
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. 为什么？

4

1 回答 1

7

让我们从头开始：

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，但 promise 的签名是constructa Tree a，因此需要a ~ Tree a与前一种情况一样。

于 2020-07-11T21:55:45.537 回答