2

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.

Tai
  • 7,684
  • 3
  • 29
  • 49
MasterYork42
  • 228
  • 2
  • 11

3 Answers3

4

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
Sam Westrick
  • 1,248
  • 1
  • 7
  • 9
  • Would I send a tuple to compound in order to send it both the base and the value of x? – MasterYork42 Mar 03 '18 at 20:05
  • The base doesn't change from iteration to iteration, so no need! Just writing the function exactly as I did in the answer will be correct. For more information, you might be interested in reading about [closures](https://en.wikipedia.org/wiki/Closure_(computer_programming)). – Sam Westrick Mar 03 '18 at 20:19
  • That makes sense such a small thing! Thank You! – MasterYork42 Mar 03 '18 at 20:30
  • No problem. I've also just edited the answer with a solution that eliminates the special case when `e = 0`, making the final code quite elegant. – Sam Westrick Mar 03 '18 at 20:40
2

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);
BearsBeetBattlestar
  • 318
  • 2
  • 13
0

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
MiltoxBeyond
  • 2,683
  • 1
  • 13
  • 12
  • The OP requires that one use the `compound` function he/she listed above. – Tai Mar 03 '18 at 18:47
  • The main problem i'm running into is how to keep the original base number b and use that for the multiplication. I feel like I have to use multiple calls to compound, but not sure how to do that. – MasterYork42 Mar 03 '18 at 18:54
  • I was thinking the same. Basically break down the multiplication to addition. 2^4 = 2*2*2*2 = 2+2+2+2+2+2+2+2. 3^5 = 3*3*3*3*3 = 3+3...+3 – MiltoxBeyond Mar 03 '18 at 18:57
  • Unfortunately I have to step out so I can't keep working on this but hopefully it gives you an idea – MiltoxBeyond Mar 03 '18 at 19:03