Wir lösen die Aufgabe: gegeben ist ein t :: Tree a, gesucht ist ein Baum s gleicher Form wie t, der in jedem Knoten das Maximum aller Schlüsselwerte von t enthält (also überall die gleiche Zahl).
Das ist überhaupt nicht schwer:
import Tree import TFold import TMap import Anamorph tmax :: Ord a => Tree a -> Maybe a -- ergibt Nothing, wenn der Baum leer ist, -- sonst Just maximum tmax = tfold ( \ l k r -> max (max l r) (Just k) ) Nothing alles_max :: Ord a => Tree a -> Tree a alles_max Leaf = Leaf alles_max t = let Just m = tmax t in fmap (const m) tDer Witz ist aber, daß es auch eine Lösung gibt, die den Baum nur einmal durchläuft. Dieses Programm wurde von Richard Bird gefunden. Wichtiger Mann für die Funktionale Programmierung.
import Tree import TFold import TMap import Anamorph ersetzen_und_max :: Ord a => a -> Tree a -> (Tree a, Maybe a) -- alle Knoten durch m ersetzen -- außerdem Maximum der Knoten ausgeben ersetzen_und_max m = tfold ( \ (l, lm) k (r, rm) -> ( Node { left = l, key = m, right = r } , max (max lm rm) (Just k) ) ) ( Leaf, Nothing ) alles_max :: Ord a => Tree a -> Tree a alles_max Leaf = Leaf alles_max t = let (s, Just m) = ersetzen_und_max m t in s