FP-As-1

Question 1

Given the following 4 function declarations in C language. Decide if the functions are immutable (pure). You need to give the reason if the function is mutable (impure). (5 pt each)

a.

int funA (char* a, int b){
	int n = 0;
	while (a[n] != '\0'){
		n++;
	} 
	return n;
}

funA is mutable. If we modify the first element of the input parameter a, the output of the function will be different. But the address of the input parameter a is not changed. Therefore, the function is mutable.

b.

int funB (char* a ,int b){
	return b+1;
}

funB is a pure function.

c.

char* funC(char* a,int b){
	int size = funA(a,0)+1;
	char* out = (char *)malloc(sizeof(char)*size));
	for(int i=0;i<size-1;i++){
		out[i]=a[i];
	}
	out[size-1]='\0';
	return out;
}

funC is mutable. Since funC uses malloc to dynamic allocate memory, each time the function is called, the memory address that allocated by malloc is different. But the address of the input parameter a is not changed. Therefore, the function is mutable.

d.

char* funD (char* a, int b){
	return a;
}

funD is a pure function.

Question 2

Given the following expressions in OCaml. What are the utop returns? What are the meanings of the returns? (4 pt each)

a)

let x = 10;;

Output:

val x : int = 10

Meaning: The variable x has been successfully defined with the type int and the value 10.

b)

1 = 1;;

Output:

- : bool = true

Meaning: The output indicates that the result of the comparison is of type bool and its value is true, which means the value is equal.

C)

match 1 with _ -> "Hi";;

Output:

- : string = "Hi"

Meaning: The output indicates that the result of the match expression is of type string and its value is "Hi".

Question 3

Given the following description of functions. Please justify the functions types. List all possible types if there are multiple. (3 pt each)

a) A constant function always returns an integer zero.

$${}^{\prime }a\to int$$

b) The function adds up two integers.

$$int\to int\to int$$

c) A function takes one input but returns nothing.

$${}^{\prime }a\to unit$$

d) A function merges two lists.

$${}^{\prime }alist{\to }^{\prime }alist{\to }^{\prime }alist$$

e) A function returns the head of a given list.

$${}^{\prime }alist{\to }^{\prime }a$$

f) A function returns the tail of a given list.

$${}^{\prime }alist{\to }^{\prime }alist$$

exception EmptyList;;
let rec tail = function
	| [] -> raise EmptyList
	| [x] -> x
	| _::t -> tail t;;

let tail  = function
	| h::t -> tail t
	| [x] -> Some x 
	| [ ] -> None;;

Question 4

Implement a recursive function called reverse, which takes a list as input and returns the reversed list. Is your implementation head recursive or tail recursive? Why? Save your source code in "Al.ml" with the reason of head/tail recursive as comments. Comments in OCaml are quoted by (* ...*) (16 pt)

(*this reverse function is a tail recursive function, since the recursive call is the last operation in the function.*)

let rec reverse_tail lst acc  =
  match lst with
  | [] -> acc
  | x :: lst -> reverse_tail lst (x::acc) ;;

let reverse lst = reverse_tail lst [];;

Question 5

a)  Is pipeline operator |> left associative, right associative, or both? Give the reason.

The pipeline operator |> is left-associative, the reason is that it applies the function on the right to the result of the function on the left.

b) Please explain partial application using the integer addition operator +. (10 pt each)

Partial application is a technique in functional programming where a function is applied to some of its arguments, resulting in a new function that takes the remaining arguments.

let add_2 =(( + )) 2;;

For example, the add_2 function is created by partially applying the + operator with the argument 2. This creates a new function that adds 2 to any integer value passed to it.

Question 6

a) Which one of the followings are correct constructor name?

$$Wrong,wrong,W1,W!,W\mathrm{\_}W,W^{\prime }w,W\mathrm{\_},\mathrm{\_}W$$

Correct: $$Wrong,W1,W_W,W'w,W_$$ Incorrect: $$wrong,W!,_W$$

b) Describe how the following code is evaluated.

match true with
| true -> 0
| true -> 1
| _ -> 1;;

The expression true is compared to the first match pattern | true -> 0. Since it matches, the corresponding value 0 is returned.

Question 7

a) What is the type of the following function? Explain your answer. (3 pt)

let fun1 f g x = f g x;;

Since f g x, f takes 2 arguments, the first argument is a function g and the second argument is x.

The function type of f is ('a -> 'b -> 'c ). So the final output type of fun1 is 'c.

g is the first argument of f. the type of g is 'a. x is the second argument of f. the type of x is 'b.

Therefore, the type of the function fun1 is ('a -> 'b -> 'c) -> 'a -> 'b -> 'c.

b) What is the type of the following function? Explain your answer. (3 pt)

let fun2 f g x = f (g x)

Since f (g x), f only takes one argument, which is the result of g x. So the type of f is 'a -> 'b. So the final output type of fun2 is 'b.

Since (g x), so g takes one argument, which is x. Suppose the type of x is 'c. Since the output of g is the input of f, the type of g is 'c -> 'a.

Therefore, the type of the function fun2 is ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.

c) Mr. Naïve defines a new type 'a under as follows. (10 pt)

type 'a under = E | S of 'a | P of 'a under * 'a under;;

Constructor E is for “empty”, S is for “single”, and P is for “pair”. Some possible values in this type can be

let u1 = E;; let u2 = S 1;; let u3 = P (S 1, E);; let u4 = P (P (S 1, S 2), S 3);; let u5 = P (E, P (S 1, P (P (S 2, E), S 3)));;

However, this type 'a under is in fact presenting the same amount of information as 'a list. Thus, construct a function unify of type under->'a list such that for example

unify u1 = [];; unify u2 = [1];; unify u3 = [1];; unify u4 = [1;2;3];; unify u5 = [1;2;3];;

Save the source code in “A1.ml”

type 'a under = E | S of 'a | P of 'a under * 'a under;;
let rec unify = function
| E -> []
| S x -> [x]
| P (x, y) -> (unify x) @ (unify y);;