I have to write a function height that takes two functions height_c and height_b, where height_b is the base case that calculates the height of a tree.

Here's what I have to write,

height :: Tree a -> Int
height = foldTree height_c height_b

height_c :: a -> Int -> Int -> Int
height_c = undefined

height_b :: Int
height_b = undefined

Also useful are the definitions of foldTree and Tree,

data Tree a
= Tip
| Bin a (Tree a) (Tree a) 
deriving (Show)

foldTree
:: (a -> b -> b -> b)   -- combining function
-> b                    -- base case
-> Tree a               -- input tree
-> b                    -- answer
foldTree c b (Bin x l r) = c x (foldTree c b l) (foldTree c b r)
foldTree c b Tip         = b

I was thinking something like

height_b Tip = 0

for the base case, simple enough.

Now in terms of height_c I'm a little lost on where to begin. I'm not exactly sure how foldTree even works so that's probably the part that is messing me up the most.

CodePudding user response：

Now in terms of height_c I'm a little lost on where to begin. I'm not exactly sure how foldTree even works so that's probably the part that is messing me up the most. Any helpful advice or explanations?

height_c takes the value of the node, the height of the left subtree, the height of the right subtree, and should return the height of the entire tree. You thus implement this with:

height_c :: a -> Int -> Int -> Int
height_c x hl hr = …

CodePudding user response：

Solved it with a push from Willem. Thank you!

height :: Tree a -> Int
height = foldTree height_c height_b

height_c :: a -> Int -> Int -> Int
height_c a hl hr = 1   max hl hr

height_b :: Int
height_b = 0