高度的玫瑰树哈斯克尔

Question

考虑玫瑰树的定义如下：

data RTree a = R a [RTree a] 

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

Answer 1

这是我的最终答案。经测试，它的工作原理：

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

Answer 2

在Why Functional Programming Matters​​，作者包括代码等同于以下内容：

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 
    label (R a _) = a 
    branches (R _ bs) = bs 
    reduce = foldr 
    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 

举例说明，一棵树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 function，

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您的直接递归形式可以从这个广义的提法被回收。