Eine Funktion, die kein Fold ist

Das geht: f xs = die Länge von xs ist gerade

f = fold True ( \ x y -> not y )

Das geht nicht: g xs = die Länge von xs ist >= 2

Beweis: falls doch g = fold nil cons, dann betrachte

l0 =        Nil ; g l0 = False -- nach Spez.
l1 = Cons 4 Nil ; g l1 = False -- nach Spez.
g (Cons 2 l0) = False -- nach Spezifikation
g (Cons 2 l0) = cons 2 (g l0) = cons 2 False
g (Cons 2 l1) = True -- nach Spezifikation
g (Cons 2 l1) = cons 2 (g l1) = cons 2 False

es folgt Widerspruch False = cons 2 False = True

d.h. die Annahme (g = fold nil cons) ist falsch.