高度的玫瑰樹哈斯克爾

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您的直接遞歸形式可以從這個廣義的提法被回收。