Fold für natürliche Zahlen

data N = Z | S N deriving Show

zwei :: N
zwei = S (S Z)

nfold :: b -> (b -> b) -> N -> b
nfold z s Z = z
nfold z s (S x) = s (nfold z s x)

plus :: N -> N -> N
plus x = nfold x S

times :: N -> N -> N
times x = nfold ...

pow :: N -> N -> N
pow x = nfold ...

So definierte Funktionen sind ,,automatisch`` terminierend.