SML: Умножение с ограничениями

Question

Я пытаюсь реализовать умножение в SML с несколькими ограничениями. Я дал следующую add функции:

fun add (0 : int, m : int) : int = m 
    | add (n : int, m : int) : int = 1 + add(n-1, m) 

Я пытаюсь написать функцию, что mult (m, n) рекурсивно вычисляет произведение т и п, для любых двух натуральных чисел m и n. В вашей реализации может использоваться функция add, упомянутая выше, и - (вычитание), но она может не использовать + или *.

Вот моя попытка:

fun multiply(0 : int, m : int) = 0 
    | multiply(n : int, 0 : int) = 0 
    | multiply(1 : int, m : int) = m 
    | multiply(n : int, 1 : int) = n 
    | multiply(~1 : int, m : int) = ~m 
    | multiply(n : int, ~1 : int) = ~n 
    | multiply(n : int, m : int) = 
     if (n > 0 andalso m > 0) then 
      add(add(0, n), multiply(n, m - 1)) 
     else 
      if (n < 0 andalso m < 0) then 
       multiply(~n, ~m) 
      else 
       if (n < 0 andalso m > 0) then 
        n - multiply(n, m - 1) 
       (* n > 0 and m < 0 *) 
       else 
        m - multiply(m, n - 1); 

Он работает, когда n и m оба положительны или оба отрицательные, но не тогда, когда один положительный, а другой отрицательный, но я не могу показаться, чтобы выяснить, моя ошибка. Например,

multiply(3, ~10) оценивает по: 0. Поэтому я считаю, что мой рекурсивный вызов достигает 0 и вызывает его оценку 0. Сказав это, мои базовые дела позаботятся об этом, поэтому я не уверен, как это будет возможно.

Идеи?

Answer 1

Изменить m - multiply(m, n - 1); на m - multiply(~m, n - 1);. (И то же самое для другой n -... линии), как вы едите, вы вычитание отрицательного числа от себя, так что вы эффективно отменяя его, и вызвав базовый случай 0.

следа:

= multiply (3, -10) 
= -10 - multiply (2, -10) 
= -10 - (-10) - multiply (1, -10) 
= -10 - (-10) - (-10) 

Как только есть (-10) - (-10) вы отправляясь multiply(0 : int, m : int) что приводит к 0, так что ваша интуиция о нем, которые инициированы было правильным.

Я понял, что вы не можете использовать +, так что вот код, который следует за этим. Постарайтесь, чтобы вы умножались, мы сохраняем основную логику одинаково, но вместо того, чтобы рекурсировать с одинаковыми числами, мы поворачиваем отрицательное число положительное, прежде чем передавать его на рекурсивный вызов.

fun multiply(0 : int, m : int) = 0 
    | multiply(n : int, 0 : int) = 0 
    | multiply(1 : int, m : int) = m 
    | multiply(n : int, 1 : int) = n 
    | multiply(~1 : int, m : int) = ~m 
    | multiply(n : int, ~1 : int) = ~n 
    | multiply(n : int, m : int) = 
     if (n > 0 andalso m > 0) then 
      add(add(0, n), multiply(n, m - 1)) 
     else if (n < 0 andalso m < 0) then 
      multiply(~n, ~m) 
     else if (n < 0 andalso m > 0) then 
      n - multiply(~n, m - 1) 
     else (* n > 0 and m < 0 *) 
      m - multiply(n - 1, ~m); 

Кроме того, несовершеннолетний придираться, но вы можете изменить add(add(0, n), multiply(n, m - 1)) к add(n, multiply(n, m - 1))