函数式编程实验1华科

函数式编程实验1/华科 任务一

下列模式能否与类型为int list的L匹配成功？如果匹配不成功，指出该模式的类型？（假设x为int类型）

x::L 成功

_::_ 成功

x::(y::L) 成功

(x::y)::L 不成功，不能int::int

[x, y] 成功

x::L 表示将x追加到列表L中，_为通配符可以表示任意类型数据。::左边必须是元素，右边是列表。

任务二

试写出与下列表述相对应的模式。如果没有模式与其对应，试说明原因。

list of length 3 [x,y,z]

lists of length 2 or 3 无

Non-empty lists of pairs (x,y)::L

Pairs with both components being non-empty lists
(x::L,y::L’)

由模式匹配，可以知道x::L匹配一个列表，L最少为[]，所以x::L匹配至少含一个元素的列表

任务三

分析下述程序段（左边括号内为标注的行号）：

(1) val x : int = 3

(2) val temp : int = x + 1

(3) fun assemble (x : int, y : real) : int =

(4) let val g : real = let val x : int = 2 2

(5) val m : real = 6.2 * (real x) 12.4

(6) val x : int = 9001 9001

(7) val y : real = m * y 37.2

(8) in y – m 24.8

(9) end

(10) in

(11) x + (trunc g) 3+24

(12) end

(13)

(14) val z = assemble (x, 3.0) 27
试问：第4行中的x、第5行中的m和第6行中的x的声明绑定的类型和值分别为什么？第14行表达式assemble(x, 3.0)计算的结果是什么？

答案都在每一行后面标注出来了，类型可以根据值看出来，ML语言严格类型检查。

任务四

指出下列代码的错误：

(* pi: real *)
val pi : real = 3.14159;

对

(* fact: int -> int *)
fun fact (0 : int) : int = 1
  | fact n = n * (fact (n - 1));

对

(* f : int -> int *)
fun f (3 : int) : int = 9
    f _ = 4;

第3行缺少 |

(* circ : real -> real *)
fun circ (r : real) : real = 2 * pi * r   

2是int pi和r是real

(* semicirc : real -> real *)
fun semicirc : real = pie * r

没有参数表，没有变量pie和r

(* area : real -> real *)
fun area (r : int) : real = pi * r * r

类型不匹配 r:int pi:real 返回real

任务五

在提示符下依次输入下列语句，观察并分析每次语句的执行结果。

3+ 4; 7

3 + 2.0; 不匹配

it + 6; 13

val it = “hello”; hello

it + “ world”; 没有重载

it + 5; 没有重载

val a = 5; 5

a = 6; false

a + 8; 13

val twice = (fn x => 2 * x);

val twice = fn : int -> int

twice a; 10

let x = 1 in x end; 错误

没有val时，比较x和1的大小

foo; 没有绑定

[1, “foo”]; 类型不符合

每一行的结果都放在对应行的后面了

任务六

函数sum用于求解整数列表中所有整数的和，函数定义如下：

(* sum : int list -> int 		*)
(* REQUIRES: true		*)
(* ENSURES: sum(L) evaluates to the sum of the integers in L. *)
fun sum [ ] = 0
 |  sum (x ::L) = x + (sum L);

完成函数mult的编写，实现求解整数列表中所有整数的乘积。

(* mult : int list -> int 		*)
(* REQUIRES: true		*)
(* ENSURES: mult(L) evaluates to the product of the integers in L. *)
fun mult [ ] = 		1	(* FILL IN *)
 |  mult (x ::L) = x*(mult L)	(* FILL IN *) 

任务七

编写函数实现下列功能：

（1）zip: string list * int list -> (string * int) list

其功能是提取第一个string list中的第i个元素和第二个int list中的第i个元素组成结果list中的第i个二元组。如果两个list的长度不同，则结果的长度为两个参数list长度的最小值。

fun zip([]:string list,[]:int list):(string*int)list=[]
 |	zip ([]:string list,L:int list):(string*int)list=[]
 |	zip (L:string list,[]:int list):(string*int)list=[]
 |	zip (str::SL,num::NL)=(str,num)::zip(SL,NL);

（2）unzip: (string * int) list -> string list * int list

其功能是执行zip函数的反向 *** 作，将二元组list中的元素分解成两个list，第一个list中的元素为参数中二元组的第一个元素的list，第二个list中的元素为参数中二元组的第二个元素的list。

- fun unzip([]:(string*int)list):((string list)*(int list))=([],[])
=  |	unzip ((str,num)::L)=let val (sl,nl)=unzip(L) in (str::sl,num::nl) end;

对所有元素L1: string list和L2: int list，unzip( zip (L1, L2)) = (L1, L2)是否成立？如果成立，试证明之；否则说明原因。

任务八

完成如下函数Mult: int list list -> int的编写,该函数调用mult 实现int list list中所有整数乘积的求解。

(* mult : int list list -> int 	*)
(* REQUIRES: true		*)
(* ENSURES: mult(R) evaluates to the product of all the integers in the lists of R. *)
 
fun Mult [ ] = 1	(* FILL IN *)
 |  Mult (r :: R) = (mult r)*(Mult R)	(* FILL IN *)

任务九

函数mult’定义如下，试补充其函数说明，指出该函数的功能。

(* mult’ : int list * int -> int 			*)
(* REQUIRES: true				*)
(* ENSURES: mult’(L, a) evaluates to the product of the integers in L and save in a (* FILL IN *) 	*)
fun mult’ ([ ], a) = a
 |  mult’ (x :: L, a) = mult’ (L, x * a);

利用mult’定义函数Mult’ : int list list * int -> int，使对任意整数列表的列表R和整数a，该函数用于计算a与列表R中所有整数的乘积。该函数框架如下所示，试完成代码的编写。

fun Mult’ ( [ ], a) = a	(* FILL IN *)
 |  Mult’ (r::R, a) = Mult'(R,a*(mult' (r,a)) (* FILL IN *)

任务十

编写递归函数square实现整数平方的计算，即square n = n * n。

要求：程序中可调用函数double，但不能使用整数乘法（*）运算。

(* double : int -> int *)
(* REQUIRES: n >= 0 *)
(* ENSURES: double n evaluates to 2 * n.*)
fun double (0 : int) : int = 0
    | double n = 2 + double (n - 1)
fun square (0:int):int=0 
   | square n=square(n-1) +double(n)-1;