时间戳

首页 > 解决方案 > 如何在 SML 中仅使用加法函数和迭代函数来制作乘法函数

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

问题描述

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

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

返回 30。

然后在此基础上，我需要一个名为的函数，该函数power仅使用iterateandmultiply将第一个参数提升到第二个的幂。一个例子：

power 5 4

它应该返回 625。

任何帮助将不胜感激！

标签： smlsmlnj

解决方案

所以诀窍是用来iterate帮助你add递归应用。由于iterate是一个将函数作为参数的列表组合器，因此如果您以非常基本的方式进行此操作，可能会更简单：例如，您可以add通过递归递增/递减一来定义：

(* 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)

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

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

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不是尾递归，因为最外层的表达式 ( x + ...or ~x + ...) 没有被调用multiply（因为调用发生在 的操作数内+）。这对你来说可能不是问题，但如果是，你不能轻易写... then multiply (x + ...) (y - 1)，因为当我们x用于累加结果时，任何后续的递归调用都增加了x，这意味着我们不能再添x加到......本身......因为x现在意味着两件事：累加结果和需要什么每次递归调用添加一次。）

无论如何，要完成最后一步，您必须确定与我所做iterate的共同点。当您可以发现共同点时，您可以将其隔离并改为调用。我想修复一个可能会混淆您对以下内容的解释的空白“错误” ：addmultiplyiterateiterate

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

添加这个空格并不会改变函数的行为，但在阅读时f(f x)很容易相信它说的是“适用f于f x”，这是错误的解释。这个函数实际上说的then是“iterate使用三个参数调用：n-1,f和f x; 因为n-1绑定不如函数应用程序那么紧密，并且f x 是函数应用程序（它是左关联的），我们在它们周围添加括号；这不是必需的f。”

Inadd和multiply,y被用作计数变量，而 initerate它是n。所以名称和位置都发生了变化，这意味着multiply基于iterate必须将xandy放在正确的位置。至于确定 的值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"

由于整数没有很好的解决方案，您要么必须切换到实数类型来表示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上面的，除了xhas becomeresult和1has becomeadd和+has become *，并且没有否定情况 ( if y > 0 ... else ...)。

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

  • 应该n是什么？（有些事情要倒计时。）
  • 应该f是什么？（执行逐步计算的东西。）
  • 应该x是什么？（在逐步计算中应用的东西。）

（...所有的; 在函数的上下文和它在范围内的参数iterate中，它们可能被称为其他东西。）power

推荐阅读