Wiederholung Rekursionsschema

fold anwenden: jeden Konstruktor d. Funktion ersetzen

• Konstruktor ⇒ Schema-Argument
• ...mit gleicher Stelligkeit
• Rekursion im Typ ⇒ Anwendung auf Schema-Resultat

data Tree a = Leaf a | Branch (Tree a) (Tree a)
    Leaf   :: a -> Tree a
    Branch :: Tree a -> Tree a -> Tree a
fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
fold leaf branch t = case t of
    Leaf k -> leaf k
    Branch l r -> branch (fold leaf branch l)
                         (fold leaf branch r)
depth :: Tree a -> Int
depth = fold ( \ k -> 0 ) ( \ x y -> 1 + max x y )