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 的 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.[=21 的基本情况=]

跟踪：

= 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))

SML：实施乘法限制

SML: Implementing Multiply with Restrictions

recursion

functional-programming

sml

smlnj