Struktuelle Induktion auf Bäumen?
Aufgabe:
Betrachten wir die folgenden Funktionsdefinitionen :
data Tree a = Leaf a | Node a (Tree a) (Tree a)
sumLeaves :: Tree a -> Integer
sumLeaves (Leaf x) = 1
sumLeaves (Node _ lt rt) = sumLeaves lt + sumLeaves rt
sumNodes :: Tree a -> Integer
sumNodes (Leaf x) = 0
sumNodes (Node _ lt rt) = 1 + sumNodes lt + sumNodes rt
Beweisen Sie mittels struktureller Induktion, dass für alle endlichen Bäume t :: Tree a gilt:
sumLeaves t = sumNodes t + 1