Writing power function in Standard ML with a predefined compound function

Question

Having trouble writing a power function inStandard Ml. Im trying to write a function called exp of type int -> int -> int.

The application exp b e, for non-negative e, should return b^e.

For example, exp 3 2 should return 9. exp must be implemented with the function compound provided below. exp should not directly calls itself. Here is the compound function, it takes in a value n, a function, and a value x. All it does is it applies the function to the value x n number of times.

fun compound 0 f x = x 
  | compound n f x = compound (n-1) f (f x);

Im having trouble figuring out how to write this function without recursion, and with the restraint of having to use a function that only can use a function with one parameter. Anyone have any ideas of where to start with this?

This is what I have:

fun exp b 0 = 1  
  | exp b e = (compound e (fn x => x*x) b)  

I know that this doesn't work, since if i put in 2^5 it will do: 2*2, 4*4, 16*16 etc.

Answer 1

You could just do this instead I believe

  fun exp 0 0 = 1
  | exp b 0 = 1
  | exp b e = (compound (e - 1) (fn x => b * x ) b); 

Answer 2

You are extremely close. Your definition of exp compounds fn x => x*x which (as you noticed) is not what you want, because it is repeatedly squaring the input. Instead, you want to do repeated multiplication by the base. That is, fn x => b*x.

Next, you can actually remove the special case of e = 0 by relying upon the fact that compound "does the right thing" when asked to apply a function 0 times.

fun exp b e = compound e (fn x => b*x) 1

Answer 3

this may not be exactly 100% proper code. I sort of just now read a bit of Standard ML documentation and took some code and reworked it for your example but the general idea is the same for most programming languages.

fun foo (num, power) =
let
  val counter = ref power
  val total = 1
in
  while !counter > 0 do (
    total := !total * num
    counter := !counter - 1
  )
end;

To be more clear with some pseudo-code:

input x, pow
total = 1
loop from 1 to pow
  total = total * x
end loop
return total

This doesn't handle negative exponents but it should get you started.

It basically is a simple algorithm of what exponents truly are: repeated multiplication.

2^4 = 1*2*2*2*2 //The 1 is implicit
2^0 = 1