3

我正在做一些功课，但我已经被困了几个小时。我确信这真的很微不足道，但在挖掘了所有可用的文档后，我仍然无法理解它。任何人都可以帮我一把吗？基本上，OCaml 编程中的练习要求使用平方算法求幂来定义函数 x^n。

我看过解决方案：

   let rec exp x = function
    0 -> 1
   | n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
   | n when n mod 2 <> 0 -> let y = exp x ((n-1)/2) in y*y*x
   ;;

我特别不明白的是如何从 fun 语句中省略参数 n 以及为什么要将它用作与 x 匹配的变量，这与通过平方求幂的定义没有明显的联系。

这是我的做法：

   let rec exp x n = match n with
   0 -> 1
   | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
   | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
   ;;
4

2 回答 2

2

您的版本在语法上是正确的，产生了一个很好的答案，但执行时间很长。在您的代码中，exp递归调用两次，从而产生两倍的计算量，每次调用产生两倍的计算量，等等n=0。在解决方案中，exp只调用一次，结果存储在变量y中，然后y平方。

现在，关于语法，

let f n = match n with
  | 0 -> 0
  | foo -> foo-1

相当于：

let f = function
  | 0 -> 0
  | foo -> foo-1

该行let rec exp x = function是一个函数的请求，该函数接受两个参数：x和模式匹配中使用的未命名参数。在模式匹配中，行

 | n when n mod 2 = 0  ->

命名这个参数n。并不是说在模式匹配的每种情况下都可以使用不同的名称（即使这不太清楚）：

| n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
| p when p mod 2 <> 0 -> let y = exp x ((p-1)/2) in y*y*x
于 2012-10-21T09:45:10.927 回答
1

关键字“function”不是语法糖

match x with

但对于

fun x -> match x with

因此

let rec exp x = function

可以替换为

let rec exp x = fun y -> match y with

这当然与您的解决方案等效

let rec exp x y = match y with

请注意，我写了“y”而不是“n”以避免混淆。匹配后引入的n变量是一个新变量，因为匹配它，所以只和函数参数有关。例如，而不是

let y = x in ...

你可以写：

match x with y -> ...

在这个匹配表达式中，“y”表达式是匹配的“模式”。和任何模式一样，它将其变量（此处为 y）与匹配的值绑定。（这里是 x 的值）和任何模式一样，模式中的变量是新变量，可能会影响先前定义的变量。在您的代码中：

let rec exp x n = match n with
  0 -> 1
  | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
  | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
;;

在这两种情况下，变量 n 会影响参数 n。不过，这不是问题，因为两个具有相同名称的变量具有相同的值。

于 2012-10-23T10:09:22.723 回答