How to make a multiplication function using just addition function and iterate function in SML

Question

I have two functions, add and iterate, in SML.

fun add(x,y) = x + y

fun iterate n f x = if n > 0 then iterate (n-1) f(f x) else x;

Using those two functions only, how do I write a multiply function that for example if typed:

multiply 5 6

returns 30.

Then building off of that I need a function called power that only uses iterate and multiply to raise the first argument to the power of the second. An example:

power 5 4

It should return 625.

Any help would be greatly appreciated!

Answer 1

So the trick is to use iterate to help you with applying add recursively. Since iterate is a list-combinator that takes a function as argument, perhaps it is simpler if you go about this in a very rudimentary way: For example, you could define add by recursively incrementing/decrementing by one:

(* Written using if-then-else *)
fun add x y =
    if y = 0 then x else
    if y > 0 then add (x+1) (y-1) else add (x-1) (y+1)

(* Written using mixture of pattern-matching and if-then-else *)
fun add x 0 = x
  | add x y = if y > 0
              then add (x+1) (y-1)
              else add (x-1) (y+1)

Now, that's of course grossly inefficient and completely unnecessary because we already have +, but for the sake of demonstrating recursion on numbers, this is an example of how to progress with multiply and power (still under the assumption that we don't have iterate yet).

The general method here is recursion: Since the function takes two operands, use one as the "accumulating result" and the other as "counting variable". Because this is a simple problem, you can just use x and y as the complete environment for the function's task. In slightly larger problems you might introduce more arguments that work as temporary/intermediate results.

You can write multiply in a very similar way:

fun multiply x 0 = 0
  | multiply x y = if y > 0
                   then  x + multiply x (y-1)
                   else ~x + multiply x (y+1)

This function solves the task (although still without iterate).

(This multiply isn't tail-recursive because the outermost expression (x + ... or ~x + ...) aren't calls to multiply (since the call happens inside the operand of +). That may not be a problem to you, but if it were, you can't easily write ... then multiply (x + ...) (y - 1), since when we use x for the purpose of accumulating the result, any subsequent recursive call has increased x, which means we can no longer add x to... itself... because x means two things now: the accumulating result, and what needs to be added once per recursive call.)

Any way, to get the last step, you have to identify what iterate has in common with the add and multiply I made. When you can spot the common denominator, you can isolate it and call iterate instead. I would like to fix one whitespace "bug" that may confuse your interpretation of iterate:

fun iterate n f x = if n > 0
                    then iterate (n-1) f (f x)
                    else x;          (* ^- this space! *)

Adding this space does not change the behavior of the function, but when reading f(f x) one is tempted to believe that it says "apply f to f x", which is the wrong interpretation. What this function actually says under then is "call iterate with three arguments: n-1, f and f x; because n-1 binds less tight than function application, and f x is function application (which is left-associative), we add parentheses around them; this is not necessary for f."

In add and multiply, y is being used as the counting variable, whereas in iterate it is n. So the names and positions have changed, which means that a multiply based on iterate has to place the x and y in the right place. As for determining a value for f: How about the function that adds x to its result? You can express this function either using a lambda, (fn z => ...), or using partial application of the function add.

Lastly, with power it is much the same problem:

fun power x 0 = 1
  | power x n = if n > 0
                then x * power x (n-1)
                else raise Fail "Cannot express 1/x^n as integer"

Since there isn't a good solution for integers, you either have to switch to the real type to express 1/x^n, you can also flip the condition and get the case of n < 0 out of the picture before beginning recursion:

fun power x n =
    if n < 0 then raise Fail "Cannot express 1/x^n as integer"
    else let fun go result 0 = result
               | go result i = go (result * x) (i-1)
         in go 1 n
         end

The inner function go looks terribly much like add above, except x has become result and 1 has become add, and + has become *, and there is no negative case (if y > 0 ... else ...).

So that means you can actually use iterate instead of go as long as you for iterate n f x find good values:

• What should n be? (Something to count down.)
• What should f be? (Something that performs the stepwise calculation.)
• What should x be? (The thing that gets applied in the stepwise calculation.)

(...all in terms of iterate; they may be called something else in the context of the power function and the arguments it has in scope.)