遍歷一個多態有限二叉樹

我的樹具有以下數據類型。遍歷一個多態有限二叉樹

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

遍歷一個多態有限二叉樹

回答

相關問題