功能测试树的叶

的存在让我们说，我们拥有这个定义类型：功能测试树的叶

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

功能测试树的叶

回答

相关问题