минимальная высота в дереве

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

Вы можете использовать Пеано Nat s вместо Integer s и пусть лени (должности):

Факс:

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 

Answer 2

Вы хотите подсчитать глубину сверху и использовать возвращаемые значения minHeight для привязки других вызовов.

minHeight :: Integer -> (Maybe Integer) -> Tree -> Integer 
minHeight depth bound tree = ... 

Первоначально проходит в 0, как глубина и Nothing, как оценка (ака Infinity), на листьях возвращают меньшее из depth и bound, в противном случае если у вас есть конечный предел (Just b) и сравнить его с текущим depth.

case b of 
    Just min -> if min <= depth then return min else RECURSION 
    otherwise -> RECURSION 

Всякий раз, когда вы вычислить некоторые minHeight в рекурсии, объединить свой результат с текущим bound.

minHeight d min (Node _ t1 t2) = 
    let min1 = Just (minHeight (d + 1) min t1) in 
     (minHeight (d + 1) min1 t2) 

Answer 3

Вот решение, которое не рассчитывает ветви, глубина которых будет выше, то уже известно, один:

data Tree = Empty | Node Integer Tree Tree 

minHeight :: Tree -> Int 
minHeight = 
    loop Nothing 0 
    where 
    loop defaultDepth depth tree = 
     case defaultDepth of 
     Just x | x <= depth -> 
      x 
     _ -> 
      case tree of 
      Empty -> depth 
      Node _ left right -> 
       loop (Just (loop defaultDepth (succ depth) left)) (succ depth) right