CODEWITHSUNDEEP
haskell
user1656755
user1656755

Reputation: 1

Function to test Tree for presence of Leaves

Lets say that we have a type which has this definition :

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

What I want to make is a function which will return a Boolean. False if my binary tree contains a Leaf and True if not.

Here is my code :

tester :: Tree a -> Bool
tester (Leaf x) = False
tester (Branch y) = if (Branch (map tester y)) then True else False

I know that the main problem of this is that there is no way to evaluate (Branch (map tester y)) but I really have no idea how to fix it.

I can add a new clause, for example something like this tester (Branch y) = True, but I don't think this is a great idea.

Upvotes: 0

Views: 188

Answers (2)

nponeccop
nponeccop

Reputation: 13677

There is a more idiomatic way to write leafless than writing recursion yourself:

{-# 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

Or even shorter:

leafless :: Tree a -> Bool
leafless = null . F.toList

Also, your type of tree is called "Rose Tree" and is already in Data.Tree

Upvotes: 4

AndrewC
AndrewC

Reputation: 32475

tester wasn't a descriptive name, so I called it leafless, and thinking about leafy was much easier.

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)

We just need to negate the result to get what we wanted.

leafless :: Tree a -> Bool
leafless = not.leafy

(any :: (a -> Bool) -> [a] -> Bool and any f xs checks whether any of the elements of the list satisfy the test (predicate) f. It works like or (map f xs).)

You can't (Branch (map tester y)) because the constructor Branch has type [Tree a] -> Tree a but map tester y is of type [Bool], not [Tree a]. You didn't need to write Branch on the right hand side; you've used it correctly on the left hand side to pattern-match against branches - it's not needed any more.

Upvotes: 5

Related Questions