遍历一个多态有限二叉树

我的树具有以下数据类型。遍历一个多态有限二叉树

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

我想打印使用左到右的深度优先遍历给定树的表示。

目前，我决定采用模式匹配。

showt :: Tree a -> [Char] 
showt (Leaf a) = [a] 
...

当我尝试使用GHCI运行它，这里的错误，我得到

• Couldn't match expected type ‘Char’ with actual type ‘a’ 
     ‘a’ is a rigid type variable bound by 
     the type signature for: 
      showt :: forall a. Tree a -> [Char] 
     at 2016.hs:31:10 
    • In the expression: a 
     In the expression: [a] 
     In an equation for ‘showt’: showt (Leaf a) = [a] 
    • Relevant bindings include 
     a :: a (bound at 2016.hs:32:14) 
     showt :: Tree a -> [Char] (bound at 2016.hs:32:1)

我不明白问题出在哪里得来的。 Haskell应该推断类型，不是？

来源

2017-05-26 Pierre P.

'[A]'的类型为'[A]''同时需要showt'返回一个'[字符]'。你需要在'a'上添加'Show'约束，并使用'show'将值转换为字符串：'showt :: Show a => Tree a - > [Char]'。 – Lee

是的，Haskell推断类型。然后看看你所要求的类型（通过编写'showt :: Tree a - > [Char]'）并检查这两种类型是否兼容。他们不是。您可以修复您的需求，或者删除它并使用推断的类型，或修复您的实施。 –

那么它是不是因为一个data Tree a = ... deriving Show，这意味着a是Char。

它仅仅意味着Haskell有自动增加了一个类型的实例：

instance Show a => Show (Tree a) where 
    -- ...

因此，大家可以看到，它增加了一个类型的约束：a必须是Show一个实例，以便Tree a是Show的实例。所以我们的第一个结论是a仍然可以是任何类型。

此外，即使是a的Show一个实例，但它确实不意味着它是一个String（或Char）。这只意味着有一些功能可用，如show :: (Show a) => a -> String。

因此，有这里的一些选项：

你添加一个类型的约束，并使用show：

showt :: Show a => Tree a -> [Char] 
showt (Leaf a) = show a 
--- ...

你限制自己String类型的树木（或键入Char）：

showt :: Tree Char -> [Char] 
showt (Leaf a) = [a] 
--- ...

终于Haskell 可以推断函数的类型，但在这里您提供了一个显式类型的签名。不过，若你省略了签名，你让哈斯克尔自动地得到它：

Prelude> let showt (Leaf a) = [a] 
Prelude> :t showt 
showt :: Tree t -> [t]

来源

2017-05-26 11:28:53

遍历一个多态有限二叉树

回答

相关问题