<h1>Lab3</h1><h2>Q1</h2><p>编写函数listToTree: int list -> tree，将一个表转换成一棵平衡树</p><p>提示：可调用split函数，split函数定义如下： 如果L非空，则存在L1, x, L2，满足： split L = (L1, x, L2) 且 L = L1 @ x :: L2 且 length(L1)和length(L2)差值小于1。</p><pre><code>datatype tree = Empty | Node of tree*int*tree;

fun split (x:int list):(int list*int*int list) = 
	let 
		val ind = (List.length(x) div 2)
		val y::R = List.drop(x,ind)
		val L    = List.take(x,ind)
	in
		(L,y,R)
	end;
	
fun listToTree ([]:int list):tree = Empty
  | listToTree ([x]:int list):tree = Node(Empty,x,Empty)
  | listToTree (X:int list):tree = 
  		let 
  			val (L,x,R) = split(X)
  		in 
  			Node(listToTree(L),x,listToTree(R))
  		end;

  			
</code></pre><h2>Q2</h2><p>编写函数revT: tree -> tree，对树进行反转，使trav(revT t) = reverse(trav t)。（trav为树的中序遍历函数）。假设输入参数为一棵平衡二叉树，验证程序的正确性，并分析该函数的执行性能（work和span）</p><p><span class="math math-inline">Span_{revT} = O(d)</span></p><p><span class="math math-inline">Work_{revT} = O(n)</span></p><pre><code>datatype tree = Empty | Node of tree*int*tree;

fun trav (Empty:tree):int list = []
  | trav (Node(l,x,r):tree):int list = 
  		let 
  			val L = trav l
			val R = trav r
		in 
			L@[x]@R
		end;
		

fun revT (Empty:tree):tree = Empty
  | revT (Node(l,x,r):tree):tree = Node(revT r, x, revT l);
  


fun reverse (x:int list):int list = List.rev(x);
</code></pre><h2>Q3</h2><p>编写函数binarySearch: tree * int -> bool。当输出参数1为有序树时，如果树中包含值为参数2的节点，则返回true；否则返回false。要求：程序中请使用函数Int.compare（系统提供），不要使用&#x3C;, =, >。 datatype order = GREATER | EQUAL | LESS case Int.compare(x1, x2) of GREATER => (* x1 > x2 <em>) | EQUAL => (</em> x1 = x2 <em>) | LESS => (</em> x1 &#x3C; x2 *)</p><pre><code>datatype tree = Empty | Node of tree*int*tree;
datatype order = GREATER | EQUAL | LESS

fun binarySearch (Empty:tree,y:int):bool = false
  | binarySearch (Node(Empty,x,Empty):tree,y:int):bool = (x=y)
  | binarySearch (Node(l,x,r):tree,y:int):bool = 
  		case Int.compare(x,y) of
  			GREATER => binarySearch(l,y)
  			| EQUAL => true
  			| LESS  => binarySearch(r,y);
</code></pre><h2>Q4</h2><p>一棵minheap树定义为：</p><ol><li>t is Empty;</li><li>t is a Node(L, x, R), where R, L are minheaps and values(L), value(R) >= x	(value(T)函数用于获取树T的根节点的值）</li></ol><p>编写函数treecompare, SwapDown 和heapify：</p><pre><code>treecompare: tree * tree -> order (* when given two trees, returns a value of type order, based on which tree has a larger value at the root node *) 

SwapDown: tree -> tree (* REQUIRES the subtrees of t are both minheaps * ENSURES swapDown(t) = if t is Empty or all of t’s immediate children are empty then * just return t, otherwise returns a minheap which contains exactly the elements in t. *) 

heapify : tree -> tree (* given an arbitrary tree t, evaluates to a minheap with exactly the elements of t.  *)
</code></pre><p>分析SwapDown 和heapify两个函数的work和span</p><p><span class="math math-inline">Span_{SwapDown}=O(d)</span></p><p><span class="math math-inline">Work_{SwapDown}=O(d)</span></p><p><span class="math math-inline">Span_{heapify}=O(d^2)</span></p><p><span class="math math-inline">Work_{heapify}=O(nlogn)</span></p><pre><code>datatype tree = Empty | Node of tree*int*tree;
datatype order = GREATER | EQUAL | LESS

fun treecompare (Empty, Empty) = EQUAL
  | treecompare (X, Empty) = GREATER
  | treecompare (Empty, Y) = LESS
  | treecompare (Node(l1,x1,r1),Node(l2,x2,r2)) = Int.compare(x1,x2);
  			
fun SwapDown (Empty:tree):tree = Empty
  | SwapDown (Node(Empty,x,Empty):tree):tree = Node(Empty, x, Empty)
  | SwapDown (Node(Empty,x,r):tree):tree = 
        let  
            val Node(rl, rx, rr) = SwapDown r 
        in 
            case Int.compare(rx, x) of
                LESS => Node(Empty, rx, Node(rl, x, rr))
                | _  => Node(Empty, x,  Node(rl, rx,rr))
        end
  | SwapDown (Node(l,x,Empty):tree):tree = 
        let 
            val Node(ll,lx,lr) = SwapDown l 
        in
            case Int.compare(lx, x) of
                LESS => Node(Node(ll,x,lr), lx, Empty)
                | _  => Node(Node(ll,lx,lr),x , Empty)
        end
  | SwapDown (Node(l,x,r):tree):tree = 
  		let 
  			val Node(ll, lx, lr) = SwapDown l
  			val Node(rl, rx, rr) = SwapDown r
  		in
  			case Int.compare(lx, rx) of
  				GREATER => (case Int.compare(rx, x) of
                			LESS => Node(Node(ll,lx,lr),rx,Node(rl,x,rr))
                        	| _ => Node(Node(ll,lx,lr),x,Node(rl,rx,rr))
                            )
                | LESS  => (case Int.compare(lx, x) of
                 			LESS => Node(Node(ll,x,lr),lx,Node(rl,rx,rr))
                 			| _  => Node(Node(ll,lx,lr),x,Node(rl,rx,rr))
                            )
                | EQUAL => Node(Node(ll,lx,lr),x,Node(rl,rx,rr)) 
         end;    
         
 fun balance (T:tree):tree = listToTree(trav T);
         
 fun heapify_helper(Empty:tree):tree = Empty
   | heapify_helper(T:tree):tree = 
   		let 
            val Node(sd_l, sd_x, sd_r) = SwapDown T
   		in
   			Node( SwapDown sd_l, sd_x, SwapDown sd_r )
   		end
         
 fun heapify (T:tree):tree = heapify_helper(balance T);
</code></pre>

华中科技大学 函数式编程实验3题目与答案

[华科]函数式编程实验3

数据库

函数式编程

华中科技大学

计算机科学

亚琛工业大学

工程科学

机器人

中文

语言

社会科学

内容

数学

自然科学

图片

音乐

其他

书籍

所思

功能

收藏

瑞士-苏黎世   计算机应用科学 硕士

苏黎世联邦理工


            以最高荣誉-荣誉学士身份毕业，并且获得优秀毕业设计称号。
            曾荣获国家奖学金、国家励志奖学金、三好学生、多次共优秀青团干部，多次优秀学生干部。
            在竞赛方面曾获得美国大学生数学竞赛F奖，全国大学生数学竞赛一等奖。
            在学生工作方面，曾是华中科技大学大学生创业实践中心项目管理部部长，参与策划筹备举行挑战杯；同时还是字节跳动校园大使和启明学院AIπ团队成员。
            科研工作方面，在校期间发表一篇ACM Transaction on Data Science，并且前后参与多段科研。
            

中国-武汉   计算机科学与技术 学士

主修高级机器人动力学
                    和计算机视觉

德国-亚琛   计算机科学交换生


            将GEN算法内存开销降低到了千分之一并且速度提升了15余倍，并提出了无监督版本。
            并且申请了一项专利。
            

算法工程师 实习生

腾讯

星辰大海才是我们的归宿


            从事基因测序相关研究，利用深度学习对Oxford Nanopore基因测序电流信号进行检测与聚类
            

加拿大-蒙特利尔   MITACS暑研项目

蒙特利尔大学