Wiederholung Rekursionsschema

fold anwenden: jeden Konstruktor d. Funktion ersetzen

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

data List a  = Nil | Cons a (List a)
     Nil  :: List a
     Cons :: a -> List a -> List a
fold :: b -> (a -> b -> b) -> List a -> b
fold nil cons l = case l of
    Nil -> nil
    Cons x xs -> cons x (fold nil cons xs)
length = fold 0 ( \ x y -> 1 + y )