2019-04-19-函数式编程

2019-04-19-函数式编程

#实验提示
在’-‘提示符下直接输入SML语句,以分号结束;
表达式计算的结果缺省赋值给变量”it”;
文件的加载: use ;
如 use “d:\sml\test.sml”;
程序正确性检查：val =
如：val 42 = eval [2,4]
示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3+ 4;
3 + 2.0;
it + 6;
val it = “hello”;
it + “ world”;
it + 5;
val a = 5;
a = 6;
a + 8; 
val twice = (fn x => 2 * x);
twice a;
let x = 1 in x end;
foo;
[1, “foo”];

#实验实例1
2.完成函数mult的编写，实现求解整数列表中所有整数的乘积。
fun mult [ ] = 1 | mult (x ::L) = x*mult (L);
3.完成如下函数Mult: int list list -> int的编写,该函数调用mult 实现int list list中所有整数乘积的求解。
fun Mult [ ] = 1 | Mult (r :: R) = mult(r)*Mult(R);
4.利用mult’定义函数Mult’ : int list list * int -> int，使对任意整数列表的列表R和整数a，该函数用于计算a与列表R中所有整数的乘积。该函数框架如下所示，试完成代码的编写。

1
2
3
4
5
fun mult' ([ ], a) = a
	  | mult' (x :: L, a) = mult' (L, x * a);

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

  1. 编写递归函数square实现整数平方的计算，即square n = n * n。
    要求：程序中可调用函数double，但不能使用整数乘法（*）运算。

    1
    2
    3
    4
    5
    fun double (0 : int) : int = 0
        | double n = 2 + double (n - 1);

    fun square(0:int):int =0
    | square(x) = square(x-1)+double(x-1)+1;

  2. 定义函数divisibleByThree: int -> bool，以使当n为3的倍数时，divisibleByThree n为true，否则为false。注意：程序中不能使用取余函数’mod’。

    1
    2
    3
    4
    5
    6
    fun divisibleByThree(x:int):bool =
    if x=0 then true else 
    if x=1 then false else 
    if x=2 then false else 
    divisibleByThree(x-3)
    ;

  3. 函数evenP为偶数判断函数，即当且仅当该数为偶数时返回true。

    1
    2
    3
    fun oddP (0 : int) : bool = false
      	    | oddP 1 = true
      	    | oddP n = oddP (n - 2);

#实验实例2

1.编写函数reverse和reverse’，要求：
函数类型均为：int list->int list，功能均为实现输出表参数的逆序输出；
函数reverse不能借助任何帮助函数；函数reverse’可以借助帮助函数，时间复杂度为O(n)。

1
2
3
4
5
6
(* 1
*function: reverse string like [a,b,c] to [c,b,a]
*require:  true
*)
fun reverse [] = []
	|reverse (a::L) =  (reverse L) @ [a];
1
2
3
4
5
6
7
8
9
10
11
12
13
(* 2
*function: reverse string like [a,b,c] to [c,b,a]  by using helper
*require:  true
*)	
fun reverse' (L : int list) : int list =
    let
      fun reversehelp' (L : int list, A : int list) : int list =
        case L of
             [ ] => A
           | x::R => reversehelp' (R, x :: A)
    in
      reversehelp' (L, [ ])
    end
  1. 编写函数 interleave: int list * int list -> int list，该函数能实现两个int list数据的合并，且两个list中的元素在结果中交替出现，直至其中一个int list数据结束，而另一个int list数据中的剩余元素则直接附加至结果数据的尾部。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    	
    (* 3
    *function: cat string by seq
    *require:  true *
    *)	
    fun interleave(A : int list,B : int list):int list =
        case (A,B) of
        ([],_) => B
        |(_,[])=> A
        |(x::X,y::Y)=>x::y::interleave(X,Y)

3.编写函数listToTree: int list -> tree，将一个表转换成一棵平衡树。
提示：可调用split函数，split函数定义如下：
如果L非空，则存在L1, x, L2，满足：
split L = (L1, x, L2) 且
L = L1 @ x :: L2 且
length(L1)和length(L2)差值小于1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

	
(*4 
*function: split strinf by middle
*require:  true *
*)   
fun split [] : (int list * int * int list) = raise Fail "cannot split empty list"
    | split(l: int list) =
      let
        val mid = (length l) div 2
        val L = (List.take (l,mid))
        val x :: R = (List.drop (l,mid))
      in
        (L, x, R)
end


(*5
*function: seq list to balace tree
*require:  true *
*)   
fun listToTree ([]:int list):int tree = Empty
| listToTree (L)=
let
      val (L, x, R) = split (L)
    in
      Node (listToTree(L), x , listToTree(R))
end

4.编写函数revT: tree -> tree，对树进行反转，使trav(revT t) = reverse(trav t)。（trav为树的中序遍历函数）。假设输入参数为一棵平衡二叉树，验证程序的正确性，并分析该函数的执行性能（work和span）。

1
2
3
4
5
6
7
8
9

(*val Empty = listToTree nil	*)
	
(*5 
*function: reverser tree seq-ly
*require:  true *
*)   	
fun revT (Empty : int tree):int tree = Empty
  | revT (Node(l,x,r)) = Node (revT (r), x , revT (l))
  1. 编写函数binarySearch: tree * int -> bool。当输出参数1为有序树时，如果树中包含值为参数2的节点，则返回true；否则返回false。要求：程序中请使用函数Int.compare（系统提供），不要使用<, =, >。
1
2
3
4
5
6
7
8
9
10
11
12
13
datatype 'a tree = Empty
    | Node of 'a tree * 'a * 'a tree

(*6 
*function: search tree by seq return bool
*require:  true *
*)   	
fun binarySearch(Empty:int  tree,i: int): bool = false 
|binarySearch(Node(l,x,r), i) =
case Int.compare(x,i) of
	GREATER => binarySearch(l,i)      
    | EQUAL => true 
    | LESS => binarySearch(r,i)

#实验实例3
1.2
实验内容：
编写函数thenAddOne，要求：
函数类型为: ((int ->int) * int) -> int；
功能为将一个整数通过函数变换(如翻倍、求平方或求阶乘)后再加1。

1
2
3
4
5
6
(*平方*)
fun f1(x:int):int = x*x

(*平方+1*)
fun thenAddOne ((f1:int -> int), (x:int)) : int =
    f1 x + 1
  1. 编写函数mapList，要求：
    函数类型为: ((‘a -> ‘b) * ‘a list) -> ‘b list；
    功能为实现整数集的数学变换(如翻倍、求平方或求阶乘)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    (**)
    fun f2(x:int):bool = 
    if x=0
    then false
    else true

    (*
    mapList(f2,[1,2,0,3]);
    *)

    (*实现整数集的f数学变换*)	
    (*最终： ((‘a -> ‘b) * ‘a list) -> ‘b list
    f x1::
    		(fx2::
    				(...
    					::mapList)))
    *)
    fun mapList (f: 'a -> 'b, [] : 'a list)  : 'b list = []
      | mapList (f, x::L) = (f x)::(mapList (f, L))

3.编写函数mapList’，要求：
① 函数类型为: (‘a -> ‘b) -> (‘a list -> ‘b list)；
② 功能为实现整数集的数学变换(如翻倍、求平方或求阶乘)。
③ 比较函数mapList’和mapList，分析、体会它们有什么不同。

1
2
3
4
5
6
7
  
(*
(‘a -> ‘b) -> (‘a list -> ‘b list)；
类上，不过类型变化
*)
fun mapList' (f : 'a -> 'b) ([] : 'a list) : 'b list = []
|mapList'(f)(x::L)=(f x)::(mapList' f L);

4.编写函数findOdd，要求：

① 函数类型为: int list -> int option；
② 功能为：如果x为L中的第一个奇数，则返回SOME x；否则返回NONE

1
2
3
4

(**)	  
fun findOdd([] : int list): int option = NONE
  | findOdd(x::L) = if (x mod 2)=1 then SOME x else findOdd L

5.编写函数subsetSumOption: int list * int -> int list option，要求：
对函数subsetSumOption(L, s)：如果L中存在子集L’，满足其中所有元素之和为s，则结果为SOME L’；否则结果为NONE。

1
2
3
4
5
6
7
8
9
10
11
12
			  
(*参考找零问题*

*)					  
fun subsetSumOption (l : int list, 0 : int) : int list option = SOME []
  | subsetSumOption ([], n) = NONE
  | subsetSumOption (x::L, sum) =
  if subsetSumOption(L, sum-x) =NONE 
  then subsetSumOption(L, sum)  (*不符合，去掉x*)
  else
  SOME (x::(valOf(subsetSumOption(L, sum-x))))
  (*符合，SOME加上x*)

  1. 编写函数：
    exists: (‘a -> bool) -> ‘a list -> bool
    forall: (‘a -> bool) -> ‘a list -> bool
    对函数p: t -> bool, 整数集L: t list,
    有：exist p L =>* true if there is an x in L such that p x=true;

    exits p L =>* false otherwise.
forall p L =>* true if p x = true for every item x in L;
forall p L =>* false otherwise.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

    (*
    p传入函数
    fun foldr F z [ ] = z
        | foldr F z (x::L) = F(x, foldr F z L)=F(x, result)
    	
    递归，结果或orelse
    p a orelse
    		p b orelse
    				foldr p true L
    *)	
    fun exists (p : 'a -> bool) (l : 'a list) : bool =
        foldr (fn (a,b) => p a orelse b) false l
    	

    (*
    类上，结果与，andalso
    若foldr (Func) result object
    *)
    fun forall (p : 'a -> bool) (l : 'a list) : bool =
        foldr (fn (a,b) => p a andalso b) true l

  2. 编写函数：
    treeFilter: (‘a -> bool) -> ‘a tree -> ‘a option tree
    将树中满足条件P（ ‘a -> bool ）的节点封装成option类型保留，否则替换成NONE。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

    datatype 'a tree = Empty
        | Node of 'a tree * 'a * 'a tree


    (*
    从根节点开始，将x替换成y
    *)	
    fun treeFilter (p : 'a -> bool ) (Empty) : 'a option tree = Empty
      | treeFilter (p) (Node (l, x, r)) =
        let
          val y = if p x then SOME x else NONE
        in
          Node (treeFilter p l, y, treeFilter p r)
        end