0

假设我们有一个具有以下定义的类型：

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的内容，但我认为这不是一个好主意。

4

2 回答 2

5

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有 type[Tree a] -> Tree a但是map tester y是 type [Bool]， not [Tree a]。你不需要写Branch在右手边；您已经在左侧正确使用它来对分支进行模式匹配 - 不再需要它。

于 2012-09-08T14:04:16.847 回答
4

有一种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-08T15:01:10.690 回答