值和函式

問題: 指出以下程式碼段中的識別符號、關鍵字和特殊常量。第二個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);