Answer: False. You can make a list of functions in OCaml as long as they all have the same type. For example, [(fun x -> x + 1); (fun x -> x * 2)] is a valid (int -> int) list.

Answer: True. OCaml’s = operator performs deep structural equality, recursively comparing the contents of data structures. Physical equality (==) checks reference identity.

Answer: True. The expression x + 5 uses integer addition (+), so OCaml infers x must be of type int without any explicit annotation.

Answer: False. OCaml does not perform implicit type conversion. Since x + 5 constrains x to int, comb 2 expects an int list. Passing a float list [8.0;9.0] is a type error.

Answer: True. The accumulator can be any type, including a list. For example, fold_left (fun acc x -> x :: acc) [] [1;2;3] uses a list as the accumulator.

Answer: True. The accumulator can be any type, including a tuple. For example, fold_left (fun (s, c) x -> (s + x, c + 1)) (0, 0) [1;2;3] uses a tuple to track both sum and count.

Answer: True. OCaml has a powerful type inference system that automatically determines the types of expressions without requiring explicit type annotations.

Answer: True. A core goal of functional programming is to minimize side effects by using pure functions and immutable data.

Answer: True. In OCaml, functions are first-class values and therefore expressions. You can pass them as arguments, return them from other functions, and bind them to variables.

Answer: True. Everything is an expression, but 2 + 3 is an expression that is not a value — it must be evaluated to produce the value 5.

Answer: False. map doesn’t modify anything in place because lists are immutable in OCaml. It returns a new list.

Answer: True. Side effects occur when we have mutability, which can make it difficult to reason about program behavior.

Answer: False. Functions return only 1 thing. This function takes an int and a float and returns a bool.

Answer: True. Currying allows for this interpretation. int -> bool -> float is equivalent to int -> (bool -> float).

Answer: False. This function has type int -> int. It neither takes a function as an argument nor returns a function, so it is not a higher order function.

Answer: True. Because we use x as a function name (applying it to 3), OCaml infers this has type (int -> ’a) -> ’a. It takes a function as an argument, making it higher order.

Answer: False. A function can only return 1 type (or 1 polymorphic type). The return type is fixed at definition time.

Answer: True. This returns 4. The second let x = 4 shadows the first let x = 3. Variables are immutable, so shadowing creates a new binding rather than mutating.

Answer: False. There are no two variables with the same name, so no shadowing occurs.

Answer: True. List.map f x always produces a list of the same length as x, regardless of what f does to each element.

Answer: False. fold_left and fold_right process the list in different orders. They only produce the same result when the function f is associative and commutative (e.g., addition). For non-commutative operations like subtraction or string concatenation, the results differ.

Answer: True. In OCaml, a function body is always a single expression. There are no statements — everything is an expression that evaluates to a value.

Some benefits of immutability:

• No aliasing bugs: Since data cannot be modified, sharing references is always safe. You never have to worry about one part of your code unexpectedly changing data used elsewhere.

• Thread safety: Immutable data can be freely shared between threads without locks or synchronization, since no thread can modify the data.

• Easier reasoning: Code is easier to understand and debug because values don’t change over time. You can always rely on a value being what it was when it was created.

Answer: B. A closure consists of a function (code) and an environment mapping its free variables to their values at the time the closure was created.

Answer: Type is ’a list -> ’a list -> ’a list. The function pattern-matches on a tuple of two lists. When both are non-empty, it returns y :: xs. Since x = [] matches the wildcard case, the result is [].

OCaml REPL

   let foo x y = 
    match x,y with 
    x::xs,y::ys -> y :: xs 
    | _ -> [] ;; 
 foo [] [1;2;3] ;;

[Output]
val foo : 'a list -> 'a list -> 'a list = <fun>
- : int list = []

Answer: Type is int list -> int. The fold computes a weighted sum using the index: 3*0 + 6*1 + 9*2 = 0 + 6 + 18 = 24. The accumulator is a tuple (total, index), but let total, _ = ... destructures it to return only total.

OCaml REPL

   let foo lst = let total, _ = 
      List.fold_left 
     (fun (tot, idx) ele -> 
      (tot + ele * idx, idx + 1)) 
    (0, 0) 
    lst in total;; 
 foo [3;6;9] ;;

[Output]
val foo : int list -> int = <fun>
- : int = 24

Answer: TYPE ERROR. The first branch returns y :: xs (a list), but the second branch returns (0,0) (a tuple). These types are incompatible, so the match expression cannot be typed.

OCaml REPL

let foo x y = 
    match x,y with 
    x::xs,y::ys -> y :: xs 
    | _ -> (0,0) ;; 
 foo [] [1;2;3] ;;

[Output]
Line 4, characters 11-16:
4 |     | _ -> (0,0) ;; 
               ^^^^^
Error: This expression has type 'a * 'b
       but an expression was expected of type 'c list
Line 1, characters 1-4:
1 |  foo [] [1;2;3] ;;
     ^^^
Error: Unbound value foo

Answer: Type is int list -> int, evaluates to 0. The initial accumulator is (0, 0). Since tot starts at 0 and gets multiplied (tot*ele*idx), the result stays 0 throughout: 0*7*0 = 0, 0*4*1 = 0, 0*23*2 = 0.

OCaml REPL

   let foo lst = let total, _ = 
    List.fold_left 
    (fun (tot, idx) ele -> 
      (tot*ele*idx, idx + 1)) 
    (0, 0) 
    lst in total;; 
 foo [7;4;23] ;;

[Output]
val foo : int list -> int = <fun>
- : int = 0

Answer: Type is int list -> int list -> int list. The wildcard branch returns [9], which constrains the type to int list (not polymorphic ’a list). Since x = [] matches the wildcard, the result is [9].

OCaml REPL

   let foo x y = match x,y with 
    x::xs,y::ys -> y :: xs 
    | _ -> [9] ;; 
 foo [] [1;2;3] ;;

[Output]
val foo : int list -> int list -> int list = <fun>
- : int list = [9]

Answer: Type is int list -> int, evaluates to 20. The fold computes a weighted sum: 2*0 + 4*1 + 8*2 = 0 + 4 + 16 = 20.

OCaml REPL

   let foo lst = let total, _ = 
    List.fold_left 
    (fun (tot, idx) ele -> 
      (tot + ele * idx, idx + 1)) 
    (0, 0) 
    lst in total;; 
 foo [2;4;8] ;;

[Output]
val foo : int list -> int = <fun>
- : int = 20

Answer: Type is ’a list -> ’a list -> ’a list, but the call causes a runtime error. foo expects two lists, but (1,3) is a tuple, not a list. The function itself type-checks fine, but the call foo (1,3) [1;2;3] is a type mismatch at the call site, causing an error.

OCaml REPL

   let foo x y = match x,y with 
    x::xs,y::ys -> y :: xs 
    | _ -> [] ;; 
 foo (1,3) [1;2;3] ;;

[Output]
val foo : 'a list -> 'a list -> 'a list = <fun>
Line 1, characters 5-10:
1 |  foo (1,3) [1;2;3] ;;
         ^^^^^
Error: This expression has type 'a * 'b
       but an expression was expected of type 'c list

Answer: Type is int list -> int, evaluates to 0. Even though tot starts at 1, the first iteration multiplies by idx = 0: 1*1*0 = 0. After that, tot remains 0: 0*3*1 = 0, 0*5*2 = 0.

OCaml REPL

   let foo lst = let total, _ = 
    List.fold_left 
    (fun (tot, idx) ele -> 
      (tot * ele * idx, idx + 1)) 
    (1, 0) 
    lst in total;; 
 foo [1;3;5] ;;

[Output]
val foo : int list -> int = <fun>
- : int = 0

Answer: Type is ’a list -> ’a list list -> ’a list list. The empty case returns y (a list list), and the non-empty case returns [x]::[], which is also a list list. No operations constrain the type, so it’s polymorphic. Since x = [4] is non-empty, x = 4 and we return [[4]].

OCaml REPL

   let f x y = match x with 
    [] -> y 
    |x::xs -> [x]::[] ;; 
 f [4] [[6]] ;;

[Output]
val f : 'a list -> 'a list list -> 'a list list = <fun>
- : int list list = [[4]]

Answer: Type is bool -> bool -> bool. The then branch returns b and the else branch returns a < true. Since a < true compares a with a bool, a : bool. Since b > a compares b with a, b : bool. The call passes 2.0 (a float) for a, which doesn’t match — Error.

OCaml REPL

let f a b = 
    if b > a then b 
    else a < true ;; 
 f 2.0 false;;

[Output]
val f : bool -> bool -> bool = <fun>
Line 1, characters 3-6:
1 |  f 2.0 false;;
       ^^^
Error: The constant 2.0 has type float but an expression was expected of type
         bool

Answer: Type is int list -> int list list. The [[3]] in the empty case constrains the type to int. Since x = [4] is non-empty, x = 4 and we return [[4]].

OCaml REPL

   let f x = match x with 
    [] -> [[3]] 
    |x::xs -> [x]::[] ;; 
 f [4];;

[Output]
val f : int list -> int list list = <fun>
- : int list list = [[4]]

Answer: Type is bool -> bool -> bool -> bool. a < true forces a : bool, b > a forces b : bool, and c must match the return type bool. The call passes a function fun x y -> x > y for c, but c : bool, so this is a type error at the call site — Error.

OCaml REPL

   let f a b c = 
    if b > a then c 
    else a < true ;; 
 f true false (fun x y -> x > y);;

[Output]
val f : bool -> bool -> bool -> bool = <fun>
Line 1, characters 14-32:
1 |  f true false (fun x y -> x > y);;
                  ^^^^^^^^^^^^^^^^^^
Error: This expression should not be a function, the expected type is bool

Answer: Type is int list -> int list list -> int list list. The [2] and [4] constrain the type to int. Since x = [4] is non-empty, it matches the _::xs pattern first (patterns are tried in order), returning [[2]].

OCaml REPL

   let f x y = match x with 
    [] -> y 
    |_::xs -> [2]::[] 
    |4::xs -> [4]::[];; 
 f [4] [[6]] ;;

[Output]
Line 4, characters 5-10:
4 |     |4::xs -> [4]::[];; 
         ^^^^^
Warning 11 [redundant-case]: this match case is unused.
val f : int list -> int list list -> int list list = <fun>
- : int list list = [[2]]

Answer: Type is bool -> bool -> bool. a < true forces a : bool. b > a forces b : bool. The then branch 1.3 < 4.6 is a bool expression that evaluates at function call time. The call passes 1.3 (a float) for b, which doesn’t match — Error.

OCaml REPL

   let f a b = 
    if b > a then (1.3 < 4.6) 
    else a < true ;; 
 f true 1.3;;

[Output]
val f : bool -> bool -> bool = <fun>
Line 1, characters 8-11:
1 |  f true 1.3;;
            ^^^
Error: The constant 1.3 has type float but an expression was expected of type
         bool

Answer: Type is ’a list -> ’a list list -> ’a list list. Same function as (a) — no operations constrain the type. Since x is non-empty, x = (1,2) and we return [[(1,2)]].

OCaml REPL

   let f x y = match x with 
    [] -> y 
    |x::xs -> [x]::[] ;; 
 f [(1,2);(3,4)] [[(6,7)]] ;;

[Output]
val f : 'a list -> 'a list list -> 'a list list = <fun>
- : (int * int) list list = [[(1, 2)]]

Answer: Type is bool -> bool -> bool. a < true forces a : bool, b > a forces b : bool. The then branch "hello" < "bye" is a bool expression. The call passes a function fun x -> x < 1 for a, which doesn’t match bool — Error.

OCaml REPL

   let f a b = 
    if b > a then ("hello" < "bye") 
    else a < true ;; 
 f (fun x -> x < 1) false;;

[Output]
val f : bool -> bool -> bool = <fun>
Line 1, characters 3-19:
1 |  f (fun x -> x < 1) false;;
       ^^^^^^^^^^^^^^^^
Error: This expression should not be a function, the expected type is bool

Answer: Type is ’a list -> ’a -> ’a list. x is matched as a list and y is consed onto xs, so y is an element (not a list). No operations force a specific type, so it’s polymorphic. Since x = [], the first branch matches and returns [].

OCaml REPL

   let f x y = match x with 
    [] -> [] 
    |x::xs -> y :: xs ;; 
 f [] [1;2;3] ;;

[Output]
val f : 'a list -> 'a -> 'a list = <fun>
- : int list list = []

Answer: Type is int list -> int -> int list. The [1] in the first branch constrains the type to int list. The call f [] [1;2;3] passes a list [1;2;3] as y, but y has type int, so this is a type error at the call site — the function type-checks but the call causes an error.

OCaml REPL

     let f x y = match x with 
    [] -> [1] 
    |x::xs -> y :: xs ;; 
 f [] [1;2;3] ;;

[Output]
val f : int list -> int -> int list = <fun>
Line 1, characters 6-13:
1 |  f [] [1;2;3] ;;
          ^^^^^^^
Error: This constructor has type 'a list
       but an expression was expected of type int

Answer: Type is int list -> int -> int list. The [14] constrains types to int. The call passes [1;2;3] (a list) as y, but y should be int, so this is an error at the call site.

OCaml REPL

   let f x y = match x with 
    [] -> [14] 
    |x::xs -> y :: xs ;; 
 f [1] [1;2;3] ;;

[Output]
val f : int list -> int -> int list = <fun>
Line 1, characters 7-14:
1 |  f [1] [1;2;3] ;;
           ^^^^^^^
Error: This constructor has type 'a list
       but an expression was expected of type int

Answer: TYPE ERROR. The expression a + 2.0 tries to use the integer addition operator + with a float. In OCaml, you must use +. for float addition.

OCaml REPL

   let f a b = 
    if b <> false then 1.0 
    else a + 2.0 ;; 
 f 2.0 false;;

[Output]
Line 3, characters 13-16:
3 |     else a + 2.0 ;; 
                 ^^^
Error: The constant 2.0 has type float but an expression was expected of type
         int
Line 1, characters 1-2:
1 |  f 2.0 false;;
     ^
Error: Unbound value f

Answer: Type is int -> string -> int. a is added to 2 so it’s int, and b is compared to the string "false" so it’s string. Since b = "true" which is not "false", the else branch runs: 2 + 2 = 4.

OCaml REPL

   let f a b = 
    if b = "false" then 1 
    else a + 2 ;; 
 f 2 "true";;

[Output]
val f : int -> string -> int = <fun>
- : int = 4

Answer: Type is bool -> int -> bool. a must match the type of true, so a : bool. b is compared to 5, so b : int. The call f 2.0 false passes a float for a and a bool for b, both wrong types — runtime error.

OCaml REPL

   let f a b = 
    if b > 5 then a 
    else true ;; 
 f 2.0 false;;

[Output]
val f : bool -> int -> bool = <fun>
Line 1, characters 3-6:
1 |  f 2.0 false;;
       ^^^
Error: The constant 2.0 has type float but an expression was expected of type
         bool

Answer: Type is float -> bool -> float. a must match the type of 2.3, so a : float. b is compared to false, so b : bool. Since false > false is false, the else branch runs, returning 2.3.

OCaml REPL

   let f a b = 
    if b > false then a 
    else 2.3 ;; 
 f 2.0 false;;

[Output]
val f : float -> bool -> float = <fun>
- : float = 2.3

Answer: Type is (’a -> ’b) -> ’a list -> (’a * ’b) list. The function pairs each element x with g x. With g = fun x -> x mod 2 = 1, each element is paired with whether it’s odd.

OCaml REPL

   let rec f g lst = match lst with 
    [] -> [] 
    |x::xs -> (x, g x)::(f g xs) ;; 
 f (fun x -> x mod 2 = 1) [1;2;3] ;;

[Output]
val f : ('a -> 'b) -> 'a list -> ('a * 'b) list = <fun>
- : (int * bool) list = [(1, true); (2, false); (3, true)]

Answer: Type is (’a -> ’b) -> ’a list -> (’b * ’a) list. Note the tuple order is (g x, x), so g’s result comes first. Each element is paired with whether it’s even.

OCaml REPL

   let rec f g lst = match lst with 
    [] -> [] 
    |x::xs -> (g x, x)::(f g xs) ;; 
 f (fun x -> x mod 2 = 0) [1;2;3] ;;

[Output]
val f : ('a -> 'b) -> 'a list -> ('b * 'a) list = <fun>
- : (bool * int) list = [(false, 1); (true, 2); (false, 3)]

Answer: Type is (’a -> ’b) -> ’a list -> (’b * ’a) list. The tuple order is (g x, x). Each float has 2.0 added, and the result comes first in the pair.

OCaml REPL

   let rec f g lst = match lst with 
    [] -> [] 
    |x::xs -> (g x, x)::(f g xs) ;; 
 f (fun x -> x +. 2.0) [1.0;2.0;3.0];;

[Output]
val f : ('a -> 'b) -> 'a list -> ('b * 'a) list = <fun>
- : (float * float) list = [(3., 1.); (4., 2.); (5., 3.)]

Answer: Type is (’a -> ’b) -> ’a list -> (’a * ’b) list. The tuple order is (x, g x). Each float is doubled by g, and the original comes first in the pair.

OCaml REPL

   let rec f g lst = match lst with 
    [] -> [] 
    |x::xs -> (x, g x)::(f g xs) ;; 
 f (fun x -> x *. 2.0) [1.0;2.0;3.0];;

[Output]
val f : ('a -> 'b) -> 'a list -> ('a * 'b) list = <fun>
- : (float * float) list = [(1., 2.); (2., 4.); (3., 6.)]

Answer: Type is ’a list -> ’a list. It swaps adjacent pairs of elements. foo [1;2;3;4;5] evaluates to [2;1;4;3;5]. The first pair 1,2 becomes 2,1, the second pair 3,4 becomes 4,3, and 5 is left as-is by the wildcard case.

OCaml REPL

   let rec foo lst = 
    match lst with 
    h1::h2::t -> h2 :: h1 :: foo t 
    | _ -> lst;; 
 foo [1;2;3;4;5];;

[Output]
val foo : 'a list -> 'a list = <fun>
- : int list = [2; 1; 4; 3; 5]

Answer: Type of foo is (’a -> ’a) -> ’a -> ’a. Since f (f x) requires the output type of f to match its input type. Here f = fun x -> [List.length x] has type int list -> int list (unifying ’a = int). So f [3;6;9] = [3], then f [3] = [1]. The result is [1].

OCaml REPL

   let foo f x = f (f x);; 
 
 foo (fun x -> [List.length x]) [3;6;9];;

[Output]
val foo : ('a -> 'a) -> 'a -> 'a = <fun>
- : int list = [1]

Answer: int -> bool -> int. The else branch is ‘a+1‘, which implies ‘a‘ must be an integer. The if condition ‘b‘ must be a boolean. The function returns an integer.

Answer: 16. The ‘let x = 4‘ shadows the ‘let x = 3‘. So ‘x‘ is 4, and ‘x * x‘ is 16.

Answer: (’a -> ’b -> ’a) -> ’a -> ’b list -> ’a. This is the standard definition of ‘fold_left‘. The accumulator ‘acc‘ has type ‘’a‘, the list elements have type ‘’b‘, and the function ‘f‘ takes the accumulator and a list element and returns a new accumulator.

Answer: int list. The ‘::‘ operator prepends an element to a list. Since ‘3‘ is an ‘int‘ and ‘[1;2]‘ is an ‘int list‘, the result is an ‘int list‘.

Answer: 5. The innermost ‘let x = 3‘ shadows the outer ‘let x = 1‘. The expression ‘x + y‘ therefore evaluates to ‘3 + 2‘, which is 5.

Answer: 4. ‘f 2‘ evaluates to ‘2 + 1 = 3‘. ‘g‘ is an alias for ‘f‘, so ‘g (f 2)‘ is ‘f(3)‘, which evaluates to ‘3 + 1 = 4‘.

Answer: bool -> bool -> bool. The ‘if‘ condition ‘x‘ must be a ‘bool‘. Since the ‘else‘ branch returns ‘x‘, the return type of the function must also be ‘bool‘. The ‘then‘ branch returns ‘y‘, so ‘y‘ must also be of type ‘bool‘.

Answer: Both Option 1 and Option 3 are correct.

Answer: ‘int list -> int‘. The function takes an integer list as input, and returns the sum of the integers in the list. Thus it returns an integer.

Answer: 6. ‘a‘ is first assigned ‘1‘, and ‘b‘ is assigned ‘2‘. Then, ‘a‘ is reassigned to the value of ‘a + b‘, which is ‘1 + 2 = 3‘. Finally, the expression evaluates ‘a * b = 3 * 2 = 6‘.

Answer: float list list. Each inner list contains floats, making them float list. The outer list contains float lists, giving float list list.

Answer: ’a list -> ’a. The pattern (x::_) matches the head of any list. Since x is unconstrained, the result is polymorphic ’a list -> ’a. (A warning is produced for incomplete pattern matching since [] is unhandled.)

Answer: 6. The elements of [1;2;1;4;2;3] strictly less than 3 are 1, 2, 1, and 2. Their sum is 1 + 2 + 1 + 2 = 6.

Answer: let timesThree lst = List.map (fun x -> x *. 3.0) lst. The anonymous function multiplies each float element by 3.0 using the float multiplication operator *.

Answer: A closure that captures x = 2. Partial application of comb with x = 2 returns a function waiting for lst, with x bound to 2 in the closure’s environment.

Answer: It does not have garbage collection. OCaml DOES have automatic garbage collection. The other three statements are all true about OCaml.

Answer: Static Typing. Static typing catches type errors at compile time before the program runs, reducing the chance of runtime errors.

Answer: Improved performance. Compiled languages are translated to machine code ahead of time, which typically runs faster than interpreted code translated at runtime.

Answer: (20, 50). f’ closes over v = 2 (before rebinding), so f’ 10 = 2 * 10 = 20. After let v = 5, f v 10 = f 5 10 = 5 * 10 = 50.

Answer: (26, 6). Steps: (0,0) with 2 -> (4,1); (4,1) with 4 -> (12,3); (12,3) with 7 -> (26,6). Note: 7/2 = 3 (integer division in OCaml).

Answer: 160. map multiplies each element: [10;20;30]. Then fold sums starting at 100: 100+10+20+30 = 160.

Answer: (string * int list) list. Each element is a pair (string, int list), and the outer structure is a list of such pairs.

Answer: (’a -> ’b) -> (’b -> ’a) -> ’b -> bool. nee : ’b -> ’a requires du : ’b. huh : ’a -> ’b gives huh (nee du) : ’b. Comparing ’b > ’b returns bool.

Answer: Type error. OCaml uses ’^’ for string concatenation, not ’+’. Using ’+’ with strings causes a type error at compile time.

Answer: [2; 4; 6; 8]. y starts as false (skip), then alternates: skip 1, keep 2, skip 3, keep 4, skip 5, keep 6, skip 7, keep 8.

Answer: 36. t = a b c = (fun x y -> x*y) 2 3 = 6. d t a = (fun x y -> y x x) 6 (fun x y -> x*y) = (fun x y -> x*y) 6 6 = 36.

Answer: ["c"; "b"; "a"]. mystery reverses a list using a tail-recursive accumulator. Each head is prepended to acc, reversing the order.

Answer: 23. Sum(Num(3),Num(4)) = 3+4 = 7. Double(Num(8)) = 2*8 = 16. Sum(7, 16) = 23.

let foo = (fun a b c -> a * c + b) 7 3

Answer:

let foo c = 7 * c + 3

Answer: int -> float -> int * bool. The first argument is 3 (int), the second is 9.4 (float), and the result is a pair of int and bool. Implementation:

let f x y = (3 + x, y = 9.4)

let f a b =
  match b with
  | [] -> failwith "error"
  | x::y -> if x > 3 then y::a else b;;

Answer: y and a are both int list, so y::a is a type error (:: expects an element on the left, not a list). Change y::a to y@a.

let rec count_occ lst target =
  match lst with
  | [] -> []
  | h :: t -> (if h = target then 1 else 0) + count_occ t target

Answer: The first branch returns [] (an empty list) but the second returns an integer — a type conflict. Fix it by changing [] -> [] to [] -> 0.

let rec sec_to_last lst =
  match lst with
  | ____A____ -> ____B____
  | h::t -> ____C____
  | _ -> failwith "Not enough elements!"

Answer: Blank A: [a;b] (or a::b::[]). Blank B: a. Blank C: sec_to_last t.

let count elem lst =
  fold (fun a x -> if x = elem then ___A___ else ___B___) ___C___ lst

Answer: Blank A: a + 1. Blank B: a. Blank C: 0.

Answer:

let rec is_mod_fibonacci lst =
  match lst with
  | a::b::c::d -> (c = a + b) && is_mod_fibonacci (b::c::d)
  | _ -> true

let count_threes lst =
  fold_left (fun ____A____ -> ____B____) 0
    (____C____ (fun ____D____ -> ____E____) [] lst)

Answer: Blank A: a x. Blank B: if x = 3 then a + 1 else a. Blank C: fold_left. Blank D: a x. Blank E: a@x.

OCaml REPL

fun x y z -> match x with 
 |h::t -> (if h = 0 then y = z else false) 
 |[] -> true;;

[Output]
- : int list -> 'a -> 'a -> bool = <fun>

OCaml REPL

fun f a -> (a + 1, [f a]);;

[Output]
- : (int -> 'a) -> int -> int * 'a list = <fun>

OCaml REPL

fun x y z -> (x y) = z;;

[Output]
- : ('a -> 'b) -> 'a -> 'b -> bool = <fun>

OCaml REPL

fun x y z -> if z then [x +. 1.0] else [y];;

[Output]
- : float -> float -> bool -> float list = <fun>

OCaml REPL

fun (a, b) c -> if a + 1 = 2 then b else c true;;

[Output]
- : int * 'a -> (bool -> 'a) -> 'a = <fun>

OCaml REPL

fun x y -> match x with 
 |h::t -> [h + 1 = y] 
 |[] -> [false];;

[Output]
- : int list -> int -> bool list = <fun>

OCaml REPL

fun x y z -> if y = [] && x = z then (x, z) else (x, z);;

[Output]
- : 'a -> 'b list -> 'a -> 'a * 'a = <fun>

OCaml REPL

fun a b -> [a = b];;

[Output]
- : 'a -> 'a -> bool list = <fun>

OCaml REPL

fun f a -> if (f a) = a then 3 else 5;;

[Output]
- : ('a -> 'a) -> 'a -> int = <fun>

OCaml REPL

fun a b -> (b, a +. 2.);;

[Output]
- : float -> 'a -> 'a * float = <fun>

OCaml REPL

fun s a -> (a, (float_of_string s), a);;

[Output]
- : string -> 'a -> 'a * float * 'a = <fun>

OCaml REPL

fun b i -> [b > true, i + 3];;

[Output]
- : bool -> int -> (bool * int) list = <fun>

OCaml REPL

fun f a -> f 3;;

[Output]
- : (int -> 'a) -> 'b -> 'a = <fun>

OCaml REPL

fun f b -> f b;;

[Output]
- : ('a -> 'b) -> 'a -> 'b = <fun>

OCaml REPL

fun f a b -> f a b;;

[Output]
- : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

OCaml REPL

fun a b -> let _ = b :: a in b + 1;;

[Output]
- : int list -> int -> int = <fun>

OCaml REPL

fun a b -> if a = [] then [b] else [b];;

[Output]
- : 'a list -> 'b -> 'b list = <fun>

Answer: The literals 1 and 3 are integers, but +. is the float addition operator and requires float operands. Change them to float literals:

OCaml REPL

let f x = 1.0 +. x +. 3.0;;

[Output]
val f : float -> float = <fun>

OCaml REPL

let f a b = let x = a [1] in b + x;;

[Output]
val f : (int list -> int) -> int -> int = <fun>

a is a function from int list to int; calling a [1] gives an int bound to x. Then b + x produces an int.

OCaml REPL

let f a b c = [(b a); c];;

[Output]
val f : 'a -> ('a -> 'b) -> 'b -> 'b list = <fun>

b a applies the function b : ’a -> ’b to a : ’a, yielding a ’b. The result list [(b a); c] contains two ’b elements.

OCaml REPL

(fun x -> 3, fun x -> 3.);;

[Output]
- : 'a -> int * ('b -> float) = <fun>

This is a tuple: the first component fun x -> 3 ignores its argument and returns the int 3; the second fun x -> 3. returns the float 3.0.

Answer: ’a atree -> (’a -> ’a) -> ’a atree. The Leaf case returns t (’a atree), forcing the output type to be ’a atree. This constrains f to ’a -> ’a since f x must have type ’a.

Answer: float -> float -> float * float. The operators *. and /. are float multiplication and division, constraining x and y to float. The result is a tuple of two floats.

Answer: (int * string) list. Each element is a pair (int * string), and the whole expression is a list of such pairs.

Answer: True. Mutable variables allow state to be changed, which is a side effect. Modifying a mutable variable affects the program state beyond just returning a value.

Answer: False. Functional programming languages favor immutable data. Immutability helps avoid side effects and makes programs easier to reason about.

Answer: [1; 3; 6; 10]. The reference x is shared across all calls (captured in the closure). inc 1: x=1; inc 2: x=3; inc 3: x=6; inc 4: x=10.

Answer: 25. Step h=1: x:=5+1=6; a=0+6=6. Step h=2: x:=6+2=8; a=6+8=14. Step h=3: x:=8+3=11; a=14+11=25.

Answer: B. Imperative programming describes computation as sequences of statements and control flow (loops, conditionals). Examples: C, Java, Python.

Answer: "ab". The regex requires at least one ’c’ at the end.

Answer: (a|b)*b(a|b)*. This allows any sequence of ’a’s and ’b’s before and after a required ’b’.

Answer: ccd. It matches the c*d alternative with two c’s followed by d. "ba" reverses the order for the ab alternative. "b" matches neither alternative. "abd" is not generated by either alternative.

Answer: Binary strings that start and end with the same digit. The left alternative matches strings starting and ending with 0; the right matches strings starting and ending with 1.

Answer: @veggies. The regex has one capture group (\w+), which matches "@veggies".

Answer: ^((a|(aa))|((a|b)*(ba?a?)))?$. This covers the empty string, single a, aa, and any string ending in b, ba, or baa — all ways to avoid ending in aaa. Option 2 rejects strings ending in a or aa. Option 4 matches everything.

Answer: B. ^[0-9]+$ anchors to the full string and requires one or more digits. A matches exactly one digit; C allows the empty string (* = zero or more); D allows any string containing at least one digit anywhere (not exclusively digits).

Answer: A. ^[0-9]{5}$ matches exactly 5 digits from start to end. B allows 4–6 digits; C allows letters; D allows 5 or more digits.

Answer: ^C\w+\d+\w* — insert C after ^ to require strings to start with the letter C.

Answer: It only matches strings exactly one character long (no quantifier on the character class). The correct expression is ^[a-z]+$.

Answer: 1,,2 should be rejected but is accepted (the comma is optional and digits can be zero-length). The fixed regex is ^\d+(,\d+){2,}$.

Answer: ^id: \d{3}-\d{2}-\d{4} codename: [A-Z][A-Za-z]*$

Answer: /^-?\d+(,-?\d+,-?\d+)*$/

-?\d+ matches one integer (optional minus, then digits). (,-?\d+,-?\d+)* appends zero or more pairs of additional integers. Total count: 1 + 2k for k ≥ 0 — always odd. The anchors ^ and $ ensure the entire string matches.

Rules:

— Hours range from 00 to 12
— Minutes and seconds range from 00 to 59
— Suffix is one of am, pm, AM, or PM
— No spaces allowed

Valid: 00:11:08am, 06:35:59pm, 05:41:37AM, 08:29:21PM
Invalid: 12 AM, 15:00:04pm, 12:30PM, 03:08:25

Answer: (0[0-9]|1[0-2]):([0-5][0-9]):([0-5][0-9])(am|pm|AM|PM)

(0[0-9]|1[0-2]) matches hours 00–09 or 10–12. [0-5][0-9] matches minutes/seconds 00–59. The suffix alternation covers all four valid forms. No ^/$ anchors are needed if the full string is matched.

Answer: Every NFA can be converted to an equivalent DFA. Both recognize the class of Regular Languages.

Answer: 10*1. The NFA reads a 1 to leave state 0, loops on 0s in state 1, then reads a final 1 to reach the accept state. Examples: "11", "101", "1001".

Answer: ε|(a|b)*a. The direct ε-transition to the accept state covers the empty string. Any nonempty accepted string must end in ’a’, preceded by zero or more a’s and b’s.

Answer: CFG only. Palindromes are context-free but not regular — no regex, NFA, or DFA can recognize them. A CFG works:

S → aSa | bSb | a | b | ε

Which strings from the given list are accepted? "cmsc", "umd", "d", empty string, "cmdsc", "md"

Answer: "cmsc", "umd", and "" (the empty string). A regex such as (cmsc|umd)? would accept exactly these three strings — each branch of the alternation, plus the empty string when the whole group is optional.

Write a regular expression equivalent to the given NFA.

Answer: (ab)+|a*b?

Given the following Finite State Machine, select all strings it accepts:
A. "" (empty string)
B. ac
C. aabbca
D. abba
E. aa
F. cbb

Answer: E (aa).

Tracing each string (start = state 1, accept = state 4):

A. "": remain at state 1 — not accept. Rejected.

B. ac: 1 –a–> 3, then 3 has no c transition. Rejected.

C. aabbca: 1 –a–> 3 –a–> 4 –b–> 2 –b–> 1 –c–> 4, then 4 has no a transition. Rejected.

D. abba: 1 –a–> 3, then 3 has no b transition. Rejected.

E. aa: 1 –a–> 3 –a–> 4. State 4 is accept. Accepted. ✓

F. cbb: 1 –c–> 4 –b–> 2 –b–> 1. State 1 is not accept. Rejected.

Answer: False. CFGs are strictly more powerful than NFAs/DFAs. A counterexample: the language of palindromes over {a,...,z}. A CFG can generate palindromes (S → aSa | bSb | ... | a | b | ε), but palindromes are not regular — no NFA or DFA can recognize them.

Answer: False. NFAs and DFAs are equally expressive — every NFA can be converted to an equivalent DFA via the subset construction. Both recognize exactly the class of regular languages.

Answer: True. The string "a + a * a" can be parsed as "(a + a) * a" or "a + (a * a)", giving two distinct parse trees.

Answer: False. A parser takes a token stream (from the lexer) and produces an AST. An evaluator/interpreter takes an AST and produces a result.

Answer: "ba". The grammar generates any string of ’a’s and ’b’s that ends in an ’a’.

Answer: S → aSb | ε. This generates balanced a’s followed by b’s, including the empty string.

Answer: S → TaT → SbaT → abaT → abaa. Apply TaT, then replace leftmost T with Sb (giving SbaT), then replace leftmost S with a (giving abaT), then replace T with a (giving abaa).

Answer: S → TT; T → aTb | ε. T generates a^n b^n for any n ≥ 0. S → TT generates a^n b^n a^m b^m. Option 2 only generates a^n b^n. Option 3 generates a*b*, not necessarily equal counts.

Answer: Left recursion (A → Ab) prevents top-down parsing, and common prefixes in S (both alternatives start with r) and D (both alternatives start with t) require factoring. Fixed grammar: S → rX; X → aM | D; M → iDbA; A → bA | ε; D → tE; E → tE | ε.

Answer: S → Tb; T → aTbb | ε. T → ε gives S=b (n=0). Each T → aTbb adds one ’a’ and two b’s. So n a’s produce 2n b’s from T, plus the one ’b’ from S → Tb, giving 2n+1 b’s total.

Answer: "babab". This string can be derived by grouping S → (bab)a(b) or (b)a(bab) via S → SaS, giving two distinct leftmost derivations.

Answer: All four grammars are unambiguous.

Answer: Yes, it is regular. A generates x*. Each iteration of S produces x*yx*yx*, and S as a whole generates (x*yx*yx*)*, which is regular.

Answer: {w, c, h, i, k, e, n}. First(A)={w}. First(B)={c,h,i,k,e,n}. First(ASB) = First(A) = {w}. First(S) = {w} ∪ {c,h,i,k,e,n}. ε is excluded since neither A nor B can derive ε.

Answer: S → aSc | B; B → bB | ε. S generates matched a’s and c’s around any number of b’s produced by B.

Answer: ε and cacbb. X → ε directly gives the empty string. cacbb: X → cY → c(acY) → cac(Z) → cac(bZ) → cac(bb) = "cacbb". bbb is impossible (X must start with ε, "c", or "aa"). aaacb would require X inside aaXb to derive "ac", which no production allows.

Answer: See the NFA diagram in the original exam PDF to trace the transitions and identify the correct regex.

Answer: See the DFA diagram in the original exam PDF and simulate each string step by step.

Answer: See the NFA diagram in the original exam PDF. Apply the subset construction: each DFA state is the ε-closure of a set of NFA states, and transitions are computed for each input symbol.

Answer: m|n*p+q*. Z generates q*; Y → p+(Z) generates p+q*; X → n*(p+q*); W → m | n*p+q*.

Answer: S → aSc | aS | b. Each aSc pairs one a with one c (ensuring x ≥ y). Each aS adds an extra a. The base S → b places the required b. Examples: S → aSc → a(b)c = "abc" (x=y=1); S → aS → a(b) = "ab" (x=1, y=0); S → aSc → a(aSc)c → aa(b)cc = "aabcc" (x=y=2).

Answer:

let rec parse_S toks =
  match lookahead toks with
  | Some "a" -> let toks = match_tok toks "a" in parse_S toks
  | Some "b" -> let toks = match_tok toks "b" in parse_S toks
  | Some "c" ->
      let toks = match_tok toks "c" in
      let toks = parse_T toks in
      match_tok toks "b"
  | _ -> raise (ParseError "parse_S")

let rec parse_T toks =
  match lookahead toks with
  | Some "a" -> let toks = match_tok toks "a" in parse_T toks
  | Some "b" -> let toks = match_tok toks "b" in parse_T toks
  | Some "c" -> match_tok toks "c"
  | _ -> raise (ParseError "parse_T")

Answer: No. The grammar has left recursion: both S → Sa and S → Sb place S as the leftmost symbol. A recursive descent parse_S would immediately call itself without consuming any input, causing infinite recursion.

Answer: A tokenizer/lexer converts raw input text into a flat sequence of tokens (identifiers, keywords, numbers, operators, etc.), stripping whitespace and comments. A parser takes the token stream and constructs an abstract syntax tree (AST) representing the grammatical structure of the input according to the language grammar.

Answer: False. E → E + T is left-recursive — parse_E would immediately call parse_E again without consuming any input, causing infinite recursion. Recursive descent parsers require grammars to be free of left recursion.

Answer: S -> caL, L -> cLc | bL | epsilon. parse_S matches "c" then "a" then parse_L, giving S -> caL. parse_L’s three branches give: "c" -> cLc (match c, recurse, match c), "b" -> bL, else -> epsilon.

Answer: D. E → E + T is left-recursive because the nonterminal E appears as the leftmost symbol on the right-hand side. This causes naive recursive descent parsers to loop infinitely.

Answer: The grammar is left-associative, so 3+2+4+1 parses as ((3+2)+4)+1.

Plus(Plus(Plus(Int 3, Int 2), Int 4), Int 1)