Standard ML semifactorial using a reduce function

Question

I am following this tutorial on standard ML: http://homepages.inf.ed.ac.uk/stg/NOTES/node2.html, and I came across this problem:

The semifactorial of a positive integer n is 1 × 3 × 5 × ... × n if n is odd and 2 × 4 × 6 × ... × n if n is even. Use the reduce function to define a semifac function which calculates semifactorials.

Reduce is defined as:

fun reduce (g, e, m, n, f) =
    if m > n then e else g (reduce (g, e, m, n-1, f), f n);

I've spent a couple of hours messing around with the problem and can't find a satisfying answer which doesn't require altering the reduce function. The problem becomes easy if you redefine reduce as:

fun reduce' (g, e, m, n, f) = 
    if m > n then e else g (reduce'(g, e, m, n-2, f), f n);

With the final solution as:

 fun semifactorial n = reduce'(fn (x,y) => x * y, 1, 1, n, fn x=>x);

Which is what I think the author was trying to get at, but I'm not sure. Is there anyway to solve this without altering the definition of reduce? I'm thinking that there is some really obvious functional way to do this, but I can't see how to make reduce decrement by two instead of one (my intuition says the answer lies in choosing correct function vals for g and f).

qaphla qaphla · Accepted Answer · 2013-11-21T04:53:30

You're very close. The answer is in choosing a correct f. In particular, it's key that f can depend on n.

fun semifactorial n = reduce(fn (x,y) => x * y, 1, 1,
                             n, fn x => if x mod 2 = n mod 2 then x else 1)

should work.

Alternately, and a bit more cleanly:

fun foo n x = if (x + n) mod 2 = 0 then x else 1
fun semifactorial n = reduce((op* ), 1, 1, n, foo n x)

though this form does have potential to fail with particularly large values of n and x if your ML implementation doesn't support arbitrary precision integers.

Standard ML semifactorial using a reduce function

2 Answers