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]ではなくtype であるため、できません[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 に答える