如何在 SML 中仅使用加法函数和迭代函数制作乘法函数

Question

我在 SML 中有两个函数，add 和 iterate。

fun add(x,y) = x + y

fun iterate n f x = if n > 0 then iterate (n-1) f(f x) else x;

仅使用这两个函数，我如何编写一个 multiply 函数，例如如果键入：

multiply 5 6

returns 30.

然后以此为基础，我需要一个名为 power 的函数，它只使用 iterate 和 multiply 将第一个参数提高到第二个参数的幂。一个例子：

power 5 4

应该return625.

如有任何帮助，我们将不胜感激！

Answer 1

所以诀窍是使用 iterate 来帮助您递归地应用 add。由于 iterate 是一个将函数作为参数的 list-combinator，如果您以非常基本的方式进行此操作，也许会更简单：例如，您可以通过递归地定义 add incrementing/decrementing 一个：

(* Written using if-then-else *)
fun add x y =
    if y = 0 then x else
    if y > 0 then add (x+1) (y-1) else add (x-1) (y+1)

(* Written using mixture of pattern-matching and if-then-else *)
fun add x 0 = x
  | add x y = if y > 0
              then add (x+1) (y-1)
              else add (x-1) (y+1)

现在，这当然是非常低效且完全没有必要的，因为我们已经有了 +，但是为了演示数字的递归，这是一个如何使用 multiply 和power（仍然假设我们还没有 iterate）。

这里的一般方法是递归：由于函数有两个操作数，所以用一个作为“累加结果”，另一个作为“计数变量”。因为这是一个简单的问题，所以您可以只使用 x 和 y 作为函数任务的完整环境。在稍大的问题中，您可能会引入更多作为 temporary/intermediate 结果工作的参数。

你可以用非常相似的方式写multiply：

fun multiply x 0 = 0
  | multiply x y = if y > 0
                   then  x + multiply x (y-1)
                   else ~x + multiply x (y+1)

这个函数解决了任务（虽然还是没有iterate）。

(这个 multiply 不是 tail-recursive 因为最外层的表达式（x + ... 或 ~x + ...）没有调用 multiply （因为调用发生在 + 的操作数内）。这对你来说可能不是问题，但如果是，你就不能轻易地写 ... then multiply (x + ...) (y - 1)，因为当我们使用 x为了累加结果，任何后续的递归调用都增加了x，这意味着我们不能再将x添加到...本身...因为x意味着现在有两件事：累积结果，以及每次递归调用需要添加一次。）

无论如何，要完成最后一步，您必须确定 iterate 与我制作的 add 和 multiply 的共同点。当您可以发现共同点时，您可以将其隔离并改为调用 iterate。我想修复一个可能会混淆您对 iterate:

的解释的白色 space“错误”

fun iterate n f x = if n > 0
                    then iterate (n-1) f (f x)
                    else x;          (* ^- this space! *)

添加这个 space 不会改变函数的行为，但是当阅读 f(f x) 时，人们很容易相信它说的是“将 f 应用到 f x "，这是错误的解释。这个函数在 then 下实际上说的是“用三个参数调用 iterate：n-1、f 和 f x；因为 n-1 绑定不那么紧密而不是函数应用，而f x 是函数应用（即left-associative），我们在它们周围添加了括号；这对于f是不必要的。 “

在add和multiply中，y被用作计数变量，而在iterate中是n。所以名称和位置发生了变化，这意味着基于 iterate 的 multiply 必须将 x 和 y 放在正确的位置。至于确定 f 的值：将 x 添加到其结果的函数怎么样？您可以使用 lambda (fn z => ...) 或使用函数 add.

的部分应用来表达此函数

最后，power也是同样的问题：

fun power x 0 = 1
  | power x n = if n > 0
                then x * power x (n-1)
                else raise Fail "Cannot express 1/x^n as integer"

由于整数没有很好的解决方案，您要么必须切换到 real 类型来表达 1/x^n，你也可以翻转条件并在开始递归之前将 n < 0 的情况排除在外：

fun power x n =
    if n < 0 then raise Fail "Cannot express 1/x^n as integer"
    else let fun go result 0 = result
               | go result i = go (result * x) (i-1)
         in go 1 n
         end

内部函数 go 看起来非常像上面的 add，只是 x 变成了 result 而 1 变成了 add , 而 + 变成了 *, 并且没有负例 (if y > 0 ... else ...).

所以这意味着您实际上可以使用 iterate 而不是 go 只要您 iterate n f x 找到合适的值：

n 应该是什么？（倒数的东西。）
f 应该是什么？（执行逐步计算的东西。）
x 应该是什么？（在逐步计算中应用的东西。）

（...全部根据 iterate；在 power 函数及其范围内的参数的上下文中，它们可能被称为其他名称。）

如何在 SML 中仅使用加法函数和迭代函数制作乘法函数

How to make a multiplication function using just addition function and iterate function in SML

sml

smlnj