haskell - 树的最小高度

Question

我正在尝试优化代码:

data Tree = Empty | Node Integer Tree Tree
minHeight Empty = -1
minHeight (Node _ Empty Empty) = 0
minHeight (Node _ l     r    ) = (min (minHeight l) (minHeight r)) + 1

我的目标是不计算深度高于已知深度的分支。

Answer 1

您可以使用 Peano Nat 代替 Integer 并让懒惰完成这项工作:

data Nat = S Nat | Z deriving (Eq)

instance Ord Nat where
    min (S n) (S m) = S (min n m)
    min  _     _    = Z

instance Enum Nat where
    fromEnum  Z    = 0
    fromEnum (S n) = fromEnum n + 1

data Tree = Empty | Node Integer Tree Tree

minHeight  Empty        = Z
minHeight (Node _  l r) = S (min (minHeight l) (minHeight r))

tree = Node 0 (Node 1 tree Empty) tree

main = print $ fromEnum $ minHeight tree -- 2