240040 Topics on Compiler Construction Quiz #1
Name : 박용준
1. Define the test whether a list is empty.
|
# let empty = function [] -> true | _ -> false;; val empty : 'a list -> bool = <fun> # empty [1; 2; 3];; - : bool = false # empty [];; - : bool = true |
2. Define a function sum that takes an integer list and returns the sum of all elements from it.
|
# let rec sum l = match l with [] -> 0 | h::t -> h + sum t;; val sum : int list -> int = <fun> # sum [2; 3; 4];; - : int = 9 |
3. Define a function square that takes a list of integers and returns a new list whose elements are equal to the elements of the original list squared by themselves.
|
# let rec square = function [] -> [] | h::t -> [h*h] @ square t;; val square : int list -> int list = <fun> # square [1; 2; 3; 4];; - : int list = [1; 4; 9; 16] |
4. Define a function runnerup that takes an integer list and returns the secondly largest element among the elements.
|
# let runnerup li= let rec runnerup' l f s=match l with [] -> s | h::t -> if h>=f && f>=s then runnerup' t h f else if f>=h && h>=s then runnerup' t f h else runnerup' t f s in runnerup' li 0 0;; val runnerup : int list -> int = <fun> # runnerup [5; 2; 3; 1];; - : int = 3 # runnerup [3;8;3;9;4;1];; - : int = 8 |
5. Define a function fibseq that takes an natural number n and return a Fibonacci sequence as a list of n elements.
|
# let rec fibseq i= match i with 0 -> [1] | _ -> let rec fib' =function 0 -> 1 | 1 -> 1 | n -> fib'(n-1) + fib' (n-2) in fibseq (i-1) @ [fib' i];; val fibseq : int -> int list = <fun> # fibseq 5;; - : int list = [1; 1; 2; 3; 5; 8] |
6. Define a function symtree that take a binary tree and gives its symmetric version. The binary tree has the following shape.
|
# type bintree = Leaf | Node of bintree * int * bintree;; type bintree = Leaf | Node of bintree * int * bintree # let rec symtree = function Leaf -> Leaf | Node(l,n,r) -> Node(symtree r, n, symtree l);; val symtree : bintree -> bintree = <fun> # symtree (Node(Node(Leaf,2,Leaf),1,(Node(Node(Leaf,4,Leaf),3,Node(Leaf,5,Leaf)))));; - : bintree = Node (Node (Node (Leaf, 5, Leaf), 3, Node (Leaf, 4, Leaf)), 1, Node (Leaf, 2, Leaf)) |
7. Complete the following code fragment. The type formula represents the set of logical formulas and the function truth represents the evaluation of a logical formula.
|
# type formula = T | F | Conj of formula * formula | Disj of formula * formula | Impl of formula * formula | Neg of formula;; type formula = T | F | Conj of formula * formula | Disj of formula * formula | Impl of formula * formula | Neg of formula # let rec truth = function | T->T | F->F | Conj(f1,f2) -> if f1=F then F else f2 | Disj(f1,f2) -> if f1=T then T else f2 | Impl(f1,f2) -> if Conj (f1, Neg(f2)) = T then F else T | Neg(f) -> if f=T then F else T;; val truth : formula -> formula = <fun> # truth (Impl(Disj(T,F),Conj(T,F)));; - : formula = T |
8. Assume that the following code fragment is given.
|
# exception Undefined;; exception Undefined # type nat = O | S of nat;; type nat = O | S of nat # let rec add m = function O -> m | S n -> add (S m) n;; val add : nat -> nat -> nat = <fun> # let rec sub m n=match m,n with _,O -> m | O,_ -> raise Undefined | S a,S b -> sub a b;; val sub : nat -> nat -> nat = <fun> # let rec mul m n = match m,n with O,_ -> O | _,O -> O | S O,_ -> n | _,S O -> m | _,S a -> add (mul m a) m;; val mul : nat -> nat -> nat = <fun> # let rec div m n = if n=O then raise Undefined else if m<n then O else add (div (sub m n) n) (S O);; val div : nat -> nat -> nat = <fun> # add (S (S O)) (S O);; - : nat = S (S (S O)) # sub (S (S O)) (S O);; - : nat = S O # mul (S (S O)) (S (S (S O)));; - : nat = S (S (S (S (S (S O))))) # div (S (S (S (S (S (S O)))))) (S (S O));; - : nat = S (S (S O)) |