Integer log2 as a catamorphism?
recNat :: (Integer -&gt; a -&gt; a) -&gt; a -&gt; Integer -&gt; a
recNat s z n | n &lt;= 0    = z
             | otherwise = s (n-1) (recNat s z (n-1))
-- Exercise: Express this in terms of foldNat.

log2 :: Integer -&gt; Integer
log2 = fst . recNat (\n (c, p) -&gt; if 2*p &gt; n+1 then (c, p) else (c+1, 2*p)) (0, 1)