测试树的存在叶子的功能

Question

假设我们有一个具有此定义的类型:

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

我想要做的是一个返回布尔值的函数. False如果我的二叉树包含Leaf,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,但我认为这不是一个好主意.

Answer 1

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在右边写字; 你已经在左侧正确使用它来对分支进行模式匹配 - 它不再需要了.