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) t
Der 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