CODEWITHSUNDEEP
haskelltreenumbersheight
user3276667
user3276667

Reputation: 87

Height of a Rose Tree Haskell

Consider the following definition of Rose Trees:

data RTree a = R a [RTree a]

I need help defining the function rtHeight :: (RTree a) -> Int that calculates the height of a rose tree.

So far, I have tried the following

rtHeight R a [] = 1
rtHeight R a l = 1 + rtHeight l

However, this does not work becuase l is a list of rose trees. I have also tried the following:

rtHeight R a [] = 1
rtHeight R a l = maximum (map (rtHeight) l)

I believe this fails becuase I am not adding a level while I am going down the tree.

Upvotes: 1

Views: 2351

Answers (2)

Will Ness
Will Ness

Reputation: 71065

In Why Functional Programming Matters (PDF), the author includes a code that is equivalent to the following:

reduce_tree f g z t =
  f (label t) (reduce (g . reduce_tree f g z) z (branches t))

Using it, we can write

rtHeight t = reduce_tree f g z t
  where
    f _ y  = 1 + y      -- 1 more than maximum height of subtrees
    g x y  = max x y    -- y is maximum height of subtrees to the right
    z      = 0          -- the smallest height is 0

label    (R a _ ) = a
branches (R _ bs) = bs
reduce = foldr

As an illustration, for a tree t = R a [b,c,d], this calculates t's height as

rtHeight t = 1 + max (rtHeight b)         -- rtHeight == reduce_tree f g z
                     (max (rtHeight c)
                          (max (rtHeight d)
                               0))

That is because, for the built-in foldr function,

foldr g z [a,b,c,...,n] == g a (g b (g c (... (g n z)...)))

An interesting identity is foldr (g . h) z xs == foldr g z (map h xs), and since maximum (xs ++ [0]) == foldr max 0 xs, your direct recursive formulation of rtHeight can be recovered from this generalized formulation.

Upvotes: 3

user3276667
user3276667

Reputation: 87

Here is my final answer. Tested and it worked: 

rtHeight R a [] = 1
rtHeight R a l = 1 + maximum (map (rtHeight) l)

Upvotes: 3

Related Questions