Integer log2 as a catamorphism?

Question

Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise of 'fold' on lists) can be defined for all inductively-defined (i.e. algebraic) data types and in the particular case below, for natural numbers ("A natural number is either zero, or the successor of a natural number).

Q. Can (floor) log2 on the natural numbers (setting log2(0) to be 0) be readily expressed as a single recursion scheme (e.g. a catamorphism), as opposed to via a hylomorphism (which is an anamorphism followed by catamorphism)?

A formulation of log2 via metamorphisms is given in Martin Erwig's Metamorphic Programming. Can it instead be expressed simply as a catamorphism?

Answer 1

recNat :: (Integer -> a -> a) -> a -> Integer -> a
recNat s z n | n <= 0    = z
             | otherwise = s (n-1) (recNat s z (n-1))
-- Exercise: Express this in terms of foldNat.

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