尝试在二叉树示例中练习时出现无限类型错误

Question

在完成练习 2 here 时，我向编译器提供了这个解决方案，但遇到了无限类型错误。

flatten : Tree a -> List a
flatten tree =
  case tree of
    Empty -> []
    Node v left right ->
      [v] :: flatten left :: flatten right

这似乎与我对第一个练习的解决方案没有太大不同：

sum : Tree Int -> Int
sum tree =
  case tree of
    Empty -> 0
    Node v left right ->
        v + sum left + sum right

我想知道这个问题是否与操作顺序有关，所以我添加了括号以确保 flatten 在 :: 之前得到评估，但这似乎没有什么不同：

flatten : Tree a -> List a
flatten tree =
  case tree of
    Empty -> []
    Node v left right ->
      [v] :: (flatten left) :: (flatten right)

所以现在我被难住了。

Answer 1

:: 是 cons operator，这意味着它会将单个元素添加到列表中。它的类型签名是 a -> List a -> List a。这意味着这不是有效代码，因为第一个参数 [v] 是一个列表：

[v] :: flatten left :: flatten right -- invalid!

如果要连接两个列表，请使用连接运算符：++。您可以在示例中将 :: 替换为 ++ 以使其编译：

[v] ++ flatten left ++ flatten right

表示该行的另一种方法是连接两个列表，然后使用 cons 运算符在列表前添加 v。

v :: flatten left ++ flatten right

-- The following is the same as above, but with parentheses showing precedence
v :: (flatten left ++ flatten right)

当然有更有效的方法来做到这一点，但它突出了 cons 和连接之间的区别。

您的 sum 示例之所以有效，是因为它返回一个整数而不是一个整数列表。您在 sum 中返回的类型与树中的值相同，因此您最终得到一个聚合，而不是另一个列表。

尝试在二叉树示例中练习时出现无限类型错误

Infinite Type error while attempting exercise in Binary Tree example

elm