f :: Tree a -> b f t = case t of Leaf -> c Node { left = l, key = k, right = r } -> h (f l) k (f r)jeder Konstruktor wird durch eine Funktion ersetzt: der nullstellige Konstruktor
Leaf
durch eine nullstellige Funktion (Konstante) c
,
der dreistellige Konstruktor Node
durch eine dreistellige Funktion h
Für
c = 1 , h x k y = x + y
erhalten wir leaves
,
für
c = [], h x k y = x ++ [k] ++ y
erhalten wir inorder
.