功能測試樹的葉

的存在讓我們說，我們擁有這個定義類型：功能測試樹的葉

data Tree a = Leaf a | Branch [Tree a] deriving (Show,Eq)

我想說的是，這將返回一個布爾函數。 False如果我的二叉樹包含一個葉子，並且如果不包含，則返回True。

這裏是我的代碼：

tester :: Tree a -> Bool 
tester (Leaf x) = False 
tester (Branch y) = if (Branch (map tester y)) then True else False

我知道，這樣做的主要問題是，有沒有辦法來評估(Branch (map tester y))，但我真的不知道如何解決它。

我可以添加一個新的子句，例如像這樣的tester (Branch y) = True，但我不認爲這是一個好主意。

來源

2012-09-08 user1656755

（請注意，如果x在其他情況下爲真，否則在所有情況下都可以簡化爲x）。 – huon

這不是二叉樹 - 二元樹e是一棵樹，它的分支被定義爲'branch（Tree a）（Tree a）' – amindfv

tester不是一個描述性的名稱，所以我把它叫做leafless，想到leafy要容易得多。

leafy :: Tree a -> Bool 
leafy (Leaf x) = True    -- yup - there's a leafy 
leafy (Branch ts) = any leafy ts -- yes if there are any leaves (recursive)

我們只需要否定結果以得到我們想要的結果。

leafless :: Tree a -> Bool 
leafless = not.leafy

（any :: (a -> Bool) -> [a] -> Bool和any f xs檢查所有列表的元素是否滿足測試（謂語）f。它就像or (map f xs)。）

不能(Branch (map tester y))因爲構造Branch具有類型[Tree a] -> Tree a但是map tester y的類型是[Bool]，而不是[Tree a]。您不需要在右側寫Branch;你已經在左邊正確使用它來對分支進行模式匹配 - 它不再需要。

來源

2012-09-08 14:04:16 AndrewC

有寫leafless不是自己寫的遞歸一個更地道的方式：

{-# LANGUAGE DeriveFoldable #-} 
import qualified Data.Foldable as F 

data Tree a = Leaf a | Branch [Tree a] deriving (Show,Eq,F.Foldable) 

leafless :: Tree a -> Bool 
leafless = F.foldl (\x y -> False) True

或者更短：

leafless :: Tree a -> Bool 
leafless = null . F.toList

另外，你的樹的類型被稱爲「玫瑰樹」，是已經在Data.Tree

來源

2012-09-08 15:01:10 nponeccop

請注意，一個分支是由一個節點列表定義的，所以實際上可能有一棵樹的「提示」都是'Branch [] ' – amindfv

是的，修正:)我實際上在閱讀你的評論 – nponeccop

+1之後發現它非常不錯，特別是'null.toList'，它絕對是美麗的。這讓我很高興看到這樣的事情。我承認我覺得我應該使用'可摺疊'，但是堅持遞歸解決方案，我會使用提問者聽起來沒有經驗的藉口，所以我被允許是基本的！ – AndrewC

功能測試樹的葉

回答

相關問題