haskell - 检查一棵树是否是完美树

Question

我想编写一个 Haskell 函数来检查树是否是完美树。我知道如果一棵树的所有叶子都处于相同的深度，那么这棵树就是完美的。

我知道我会这样开始

perfectTree::Tree a -> Bool

但是鉴于我对实际定义的掌握不是太强，任何人都可以真正解释什么是完美树以及如何在 Haskell 中检查树是否完美

我应该包括我定义的数据类型如下:

data Tree a = Leaf | Node a (Tree a) (Tree a)

Answer 1

一种方法是定义辅助函数 perfectTreeHeight :: Tree a -> Maybe Int返回 Just树的高度(如果完美的话)，或 Nothing否则。这更容易实现，因为您实际上可以从递归调用中获取高度，以便可以比较它们。 (提示:使用 do 表示法)

perfectTree那么只是这个函数的一个简单的包装。

import Data.Maybe (isJust)

perfectTree :: Tree a -> Bool
perfectTree = isJust . perfectTreeHeight

perfectTreeHeight :: Tree a -> Maybe Int
perfectTreeHeight = ...