玫瑰树的高度Haskell

Question

考虑玫瑰树的以下定义：

data RTree a = R a [RTree a]

我需要帮助定义函数rtHeight :: (RTree a) -> Int来计算玫瑰树的高度。

到目前为止，我已经尝试了以下方法

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

然而，这是行不通的，因为我是一个玫瑰树的列表。我还尝试了以下几点：

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

我相信这是失败的，因为我在倒下的时候并没有增加一个水平。

Answer 1

这是我最后的答案。经过测试并发挥了作用：

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

Answer 2

在为什么函数式程序设计很重要 (PDF)中，作者包含了相当于以下内容的代码：

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

用它，我们可以写

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

作为一个例子，对于一个树t = R a [b,c,d]，它计算t的高度为

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

这是因为，对于内置的函数，

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

一个有趣的标识是foldr (g . h) z xs == foldr g z (map h xs)，由于maximum (xs ++ [0]) == foldr max 0 xs，可以从这个广义公式中恢复rtHeight的直接递归公式。