World's most popular travel blog for travel bloggers.

# Something wrong with this definition of factorial with structural recursion?

, ,
Problem Detail:

In The Algebra of Programming page 5, the authors defined structural recursion `foldn (c, h)` over natural numbers:

``f  0    = c f (n+1) = h (f n) ``

They then went on to defin factorial as follows:

``fact = outr . foldn ((0, 1), f) outr (m, n) = n f (m, n) = (m + 1, (m + 1) * n) ``

This doesn't seem right, first of all, `foldn ((0, 1), f)` does not comply to its definition, secondly, this fold will never terminate, will it?

This definition is correct. The syntax is almost Haskell code, so you can run it in a Haskell interpreter:

``foldn (c, h) = g where   g 0 = c   g n = h (g (n - 1))  fact = outr . foldn ((0, 1), f) outr (m, n) = n f (m, n) = (m + 1, (m + 1) * n) ``

Usage in ghci:

``Prelude> :load fact.hs [1 of 1] Compiling Main             ( fact.hs, interpreted ) Ok, modules loaded: Main. *Main> fact 0 1 *Main> fact 1 1 *Main> fact 2 2 *Main> fact 3 6 *Main> fact 4 24 *Main> fact 5 120 ``

I don't know what you mean by "`foldn ((0, 1), f)` does not comply to its definition. If you mean that it's missing an argument, then this is not a problem. It's a function waiting to be applied. `foldn` is a curried function: it takes an argument and returns a function, which itself takes an argument and returns something; this makes `foldn` look like a function that takes two arguments (the first of which is a pair).

You can't evaluate `foldn ((0, 1), f)` any further (except to replace it by an anonymous function for which there is no source syntax) because its definition is by case on its argument: there's no way to know which one of `g 0 = …` or `g (n+1) = …` to use until you know whether the argument is 0.

Once you pass an argument, you can evaluate the call.

``foldn ((0, 1), f) 0 = (0, 1) ``

so

``fact 0 = (outr . foldn ((0, 1), f)) 0        = outr (foldn ((0, 1), f) 0)        = outr (0, 1)        = 1  fact 1 = (outr . foldn ((0, 1), f)) 1        = outr (foldn ((0, 1), f) 1)        = outr (f (foldn ((0, 1), f) 0))        = outr (f (0, 1))        = outr (0 + 1, (0 + 1) * 1)        = outr (1, 1)        = 1 ``

I'll let you work out other values by yourself.

The computation always terminates, regardless of the function `h` (assuming only that `h` terminates), by a simple induction argument: each nested call to `foldn` is applied to a smaller integer. For any nonnegative parameter, eventually the argument will be 0 which does not involve recursion.