值和函数

问题: 指出以下代码段中的标识符、关键字和特殊常量。第二个a的值是多少？

 val a = 5
 val b = 9
 val a = 2*a+b;

标识符是a、b、*和+。关键字是val、=和;。特殊常量是5、9和2。第二个a的值是19。

问题: 构造一个包含4个位置和3个组件的元组。

 (1,1,2,3)

这是一个简单的例子，但这个也是有效的

 (1,false,(3,2),1)

问题: t 的类型是什么？

 fun f (a:int) = 2
 val t = (true,f,f 1);

答案是

 bool * (int -> int) * int

问题: 编写一个函数，对于参数 0、1 和 2 返回值 2，对于所有其他参数返回 3。

fun example(0) = 2
  | example(1) = 2
  | example(2) = 2
  | example(_) = 3;

或者

fun example(x:int) = if (x>2) then 3 else if (x<0) then 3 else 2;

问题: 编写一个函数，对于所有负参数返回 -1，对于所有正参数返回 +1，对于参数 0 返回 0。

fun example(x:int) = if (x=0) then 0 else if (x<0) then ~1 else 1;

人们可能会尝试像上面的例子一样使用模式匹配，但“~”是一个运算符，因此不能在参数模式中使用。

问题: 创建一个函数 min(a:int,b:int)，该函数返回其 2 个参数中较小的一个。用 3 种不同的方式分离参数值。使用笛卡尔参数模式，使用投影，以及使用局部声明。

使用笛卡尔参数模式

fun min(a,b) = if (a<b) then a else b;

使用投影。这里我们必须注意参数类型是 int*int 的 2 元组。值 t 将保存整个元组，因此为了比较，它必须再次被拆分。

fun min(t:int*int) = if (#1t < #2t) then #1t else #2t;

使用局部声明。

fun min(t:int*int) = let val (a,b)=t in if (a<b) then a else b end;

递归

问题: 创建一个函数 power9(x)，它计算 x 的 9 次方。最好尽可能少地使用乘法。

直接的方法可能是

fun power9(x) = x*x*x*x*x*x*x*x*x;

但这并不是一种巧妙的方法，而且它也使用了大量的乘法。我们可以在函数内部使用局部声明来缩短代码并使其更易读。

 fun power9(x) = 
 let
   val a=x*x 
   val b=a*a 
 in 
   b*b*x 
 end;

或者我们可以使用辅助函数来计算部分积。

fun power2(x) = x*x;
fun power4(x) = power2(x)*power2(x);
fun power9(x) = power4(x)*power4(x)*x;

但这仍然不是真正智能的。对于像 power66() 这样的函数，我们必须编写大量的代码。以下代码使用递归函数调用来计算 x 的 n 次方。

fun power(x,n) = if (n=0) then 1 else power(x,n-1)*x;

可以改写为

fun power(x,0) = 1
  | power(x,n) = power(x,n-1)*x;

问题: 计算来自 2 个正整数参数的最大公约数。

使用欧几里得算法，我们构造递归函数

fun gcd(a,0) = a
  | gcd(a,b) = gcd(b,a-b*(a div b));

问题: 计算 mul(n,z)=n*z，不使用 * 运算符，对于 $n\in \mathbb {N}$ 和 $z\in \mathbb {Z}$ 。

fun mul(n:int, z:int) = if (n=1) then z else z + mul(n-1,z);

fun h(a:int, n:int, z:int) = if (n=1) then z + a else h(a+z,n-1,z);
fun mul(n:int, z:int) = h(0,n,z);

问题: 只使用加法和递归计算 power2(n)。(提示: 可以将平方函数重写为自然数的求和。)

要计算的和是 $power2(n)=\sum _{k=n}^{1}2*n-1$ ，它是 $\mathbb {N}$ 中前 n 个奇数元素的和。换句话说， $power2(n)=1+3+\dots +2*n-1$ 。

fun power2(1) = 1
  | power2(n) = n+n-1 + power2(n-1);