3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$
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) 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.