Algorithmen-Schablone f. Bäume

leaves :: Tree a -> Int -- Anzahl der Blätter
leaves Leaf = 1
leaves t = leaves (left t) + leaves (right t)

inorder :: Tree a -> [a] -- Schlüssel-Reihenfolge
inorder Leaf = []
inorder t    =    inorder (left t) 
    ++ [key t] ++ inorder (right t)
Gemeinsame Struktur (Rekursions-Schema):
tfold f z Leaf = z
tfold f z t    = 
 f(tfold f z (left t))(key t)(tfold f z (right t))


leaves  = tfold (\ l k r -> l         + r) 1  
inorder = tfold (\ l k r -> l ++ [k] ++ r) [] 
Aufgab: Typ von tfold?



Johannes Waldmann 2004-11-30