ML语言/函数式编程原理

compare: int *int ->order

定义新的数据类型order

datatype order=LESS|EQUAL|GREATER;
fun compare(x:int,y:int):order=
		if x 
二、排序结果判断sorted 
sorted : int list->bool （判断升序）
 
fun sorted [] =true
	|	sorted [x] =true
	| sorted (x::y::L)=
		(compare(x,y)<>GREATER andalso sorted(y::L));
 
 
 
其中compare(x,y)<>GREATER表示不等于GREATER，即小于等于
 
 
三、插入排序 
1.整数的插入ins 
ins : int*int list -> int list （有序list中插入一个int）
 
fun ins (x,[])=[x]
	| ins(x,y::L)=case compare(x,y) of
								GREATER=>y::ins(x,L)
								| _ =>x::y::L;
 
2.插入排序 
isort : int list ->int list （无序list得到有序list）
 
fun isort [] =[]
| isort (x::L)=ins(x,isort L);
 
3.另一个插入排序isort’ 
isort’ : int list -> int list （无序list得到有序list）
 
fun isort' [] = []
| isort' [x]=[x]
| isort' (x::L)=ins(x,isort' L);
 
四、归并排序 
1.表的分割split 
split : int list ->int list * int list
 
fun split [] =([],[])
	| split [x] = ([x],[])
	| split (x::y::L)=
			let val (A,B)=split L
			in (x::A,y::B)
			end
 
2.表的合并merge 
merge : int list * int list ->int list （两个有序表合并成一个有序表）
 
fun merge(A,[])=A
 |  merge([],B)=B
 |  merge(x::A,y::B)=case compare(x,y) of
 													LESS => x::merge(A,y::B)
 													|EQUAL => x::y::merge(A,B)
 													|GREATER => y::merge(s::A,B);
 
3.mergesort 
Most : int list -> int list （无序表到有序表）
 
fun msort []=[]
	| msort [x]=[x]
	| msort L=let
							val (A,B)=split L
						in
							merge(msort A,msort B)
						end
 
fun msort []=[]
	| msort [x]=[x]
	| msort L=let
						 	val (A,B)=split L
						 	val A'=msort A
						 	val B'=msort B
						in	 merge(A',B')
						end
 
五、新的类型-tree 
 
 
通过tree的相关训练，真的可以更加深刻的理解递归
 
 
定义新的类型tree
 
datatype tree =Empty | Node of tree*int*tree;
 
Node(t1,x,t2) t1,t2都是tree，x是int
 
1.树的大小 
fun size Empty=0
	| size(Node(t1,_,t2))=size t1 +size t2 +1;
 
2.树的深度 
fun max(x,y):int=if x>y then x else y;
fun depth Empty = 0
	|	depth(Node(t1,_,t2))=max(depth t1,depth t2)+1;
 
3.树的遍历 
中序遍历：先左子树、再根节点、最后右子树
 
fun trav Empty = []
	| trav(Node(t1,x,t2))=trav t1 @ (x::trav t2);
 
4.树的拆分 
split:int list -> int list* int list
 
fun split [] =([],[])
	| split [x]=([x],[])
	|	split (x::y::L)=
			let val (A,B)=split L
			in (x::A,y::B)
			end
 
SplitAt : int*tree->tree*tree 对一个有序树进行拆分
 
应用递归的想法 SplitAt得到的是两个有序数
 
fun SplitAt(y,Empty)=(Empty,Empty)
	| SplitAt(y,Node(t1,x,t2))=
			case compare(x,y) of
				GREATER => let
										val(l1,r1)=SplitAt(y,t1)
									 in (l1,Node(r1,x,t2))
									 end
			 	| _			=> let
			 							val (l2,r2)=SplitAt(y,t2)
			 						 in (Node(t1,x,l2),r2)
			 						 end
 
5.数的合并 
Merge : tree*tree -> tree 对两个有序树合并
 
应用递归的想法，Merge能将两个有序树合并成一个有序树
 
fun Merge(Empty,t2)=t2
	| Merge(Node(l1,x,r1),t2)=let
															val(l2,r2)=SplitAt(x,t2)
														in
															Node(Merge(l1,l2),x,Merge(r1,r2))
 
6.树的归并排序 
Msort : tree -> tree 用一个无序树得到有序树
 
fun Msort Empty=Empty
	| Msort (Node(t1,x,t2))=
			Ins(x,Merge(Mosrt t1,Msort t2))
 
六、程序的并行执行 
fun Merge(Empty,t2)=t2
	| Merge(Node(l1,x,r1),t2)=let val(l2,r2)=Split(x,t2)
														in Node(Merge(l1,l2),x,Merge(r1,r2))
														end
 
Merge(Mosrt t1,Mosrt t2)
 
Merge串行执行的时间开销为分别对t1，t2执行Msort的开销之和+c
 
Merge并行执行的时间开销为分别对t1和t2执行的Msort开销的最大值+c
 
用“span”表示程序在足够多的并行处理器上的时间开销
 
1.Ins函数的span 
Ins : int*tree-> tree
 
fun Ins(x,Empty)=Node(Empty,x,Epmty)
	|	Ins(x,Node(t1,y,t2))=
			case compare(x,y) of
				GREATER => Node(t1,y,Ins(x,t2))
			| 		_ 	=> Node(Ins(x,t1),y,t2)
 
 
 
平衡二叉树：一棵空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 
 
Sins(d) is O(d)
 
2.SplitAt函数的span 
SplitAt : int*tree -> tree*tree
 
fun SplitAt(y,Empty)=(Empty,Empty)
	| SplitAt(y,Node(t1,x,t2))=
			case compare(x,y) of
				GREATER => let
										  val(l1,r1)=SplitAt(y,t1)
										in (l1,Node(r1,x,t2))
										end
			 | 		_ 	=> let 
			 								val(l2,r2)=SplitAt(y,t2)
			 							in (Node(t1,x,l2),r2)
			 							end
 
SSplitAt(d) is O(d)
 
3.Merge函数的span 
Merge : tree * tree -> tree
 
fun Merge (Empty, t2) = t2
	| Merge (Node(l1,x,r1), t2) = let
																	val (l2, r2) = SplitAt(x, t2)
																in
																	Node(Merge(l1, l2), x, Merge(r1, r2))
																end
 
SMerge(d) is O(d2)
 
4.Msort函数的span 
Msort : tree -> tree
 
fun Msort Empty = Empty
	| Msort (Node(t1,x,t2)) =
					Ins(x, Merge(Msort t1, Msort t2))
fun Msort Empty = Empty
	| Msort (Node(t1, x, t2)) =
					Rebalance(Ins (x, Merge(Msort t1, Msort t2)))
 
SMsort(d) is O(d3)
 
七、多态类型 
fun split [] = ([], [])
	| split [x] = ([x], [])
	| split (x::y::L) =
					let val (A,B) = split L in (x::A, y::B) end
 
多态的好处：
 
 
避免写较多多余的代码
 
 
便于维护