Запись степенной функции в стандартном ML с предопределенной составной функцией

Question

Возникли проблемы при написании степенной функции в стандарте Ml. Я пытаюсь написать функцию под названием exp типа int -> int -> int,

Приложение exp b eдля неотрицательных e, должен вернуться b^e,

Например, exp 3 2 должен вернуться 9. exp должен быть реализован с помощью функции compound предоставлено ниже. exp не должен напрямую называть себя. Здесь compound функция, она принимает значение n, функция и значение x, Все, что он делает, это применяет функцию к значению x n количество раз.

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

У меня возникли проблемы с выяснением, как написать эту функцию без рекурсии, и с ограничением необходимости использовать функцию, которая может использовать функцию только с одним параметром. У кого-нибудь есть идеи, с чего начать?

Вот что у меня есть:

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

Я знаю, что это не сработает, так как если я введу 2^5, то получится: 2*2, 4*4, 16*16 и т. Д.

Answer 1

Вы можете просто сделать это вместо этого, я верю

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

Answer 2

Вы очень близки Ваше определение exp соединений fn x => x*x что (как вы заметили) не то, что вы хотите, потому что это многократно возводит в квадрат входные данные. Вместо этого вы хотите сделать повторное умножение на основание. То есть, fn x => b*x,

Затем вы можете удалить специальный случай e = 0 полагаясь на тот факт, что compound "делает правильные вещи", когда его попросили применить функцию 0 раз.

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

Answer 3

Это может быть не совсем правильный код. Я только сейчас прочитал немного документации по стандартному ML, взял некоторый код и переработал его для вашего примера, но общая идея та же самая для большинства языков программирования.

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

Чтобы быть более понятным с некоторым псевдокодом:

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

Это не обрабатывает отрицательные показатели, но это должно помочь вам начать.

Это в основном простой алгоритм того, что в действительности представляют показатели: повторное умножение.

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