Question

problem 1: basics total 4 pts
true false
list.length x = (list.length (list.map f x)) for all valid f and x (i.e. assume list.map f x compiles) (t) (f)
if fold_left f a l compiles and results in value v then fold_right (fun x a -> f a x) l a should also result in v (t) (f)
in ocaml the entire function body is a single expression (t) (f)
ocaml lists are immutable. list 2 benefits of immutability in functional programming.

problem 2: ocaml typing and evaluating total 6 pts
give the type for the following functions foo and give what the following function call evaluates to. if there is a type error in the function, put \type error\ for the type, and put \error\ for the evaluation. if the function call causes an error for any reason, put \error\ for the evaluation.

(a) 3 pts
let rec foo lst =
match lst with
h1::h2::t -> h2 :: h1 :: foo t
| _ -> lst;;
foo 1;2;3;4;5 ;;
type of foo:
evaluation:

(b) 3 pts
let foo f x = f (f x);;
foo (fun x -> list.length x) 3;6;9 ;;
type of foo:
evaluation:

Explanation:

🆕 New Concept Discovered: Functional Programming Semantics
Understanding list transformations, fold equivalence, and type inference in OCaml.

---

Problem 1: Basics

Step 1: Analyze Statement 1

• Statement: List.length x = (List.length (List.map f x)) for all valid f and x.
• Reasoning: The List.map function applies a function f to each element of a list x, producing a new list of the exact same length. Therefore, the length of the list remains unchanged.
• Answer: True (T)

Step 2: Analyze Statement 2

• Statement: If fold_left f a l compiles and results in value v, then fold_right (fun x a -> f a x) l a should also result in v.
• Reasoning: fold_left processes elements from left to right (associating to the left), whereas fold_right processes elements from right to left (associating to the right). Even if we swap the argument order in the combining function using (fun x a -> f a x), the order of operations (associativity) is different. For non-associative operations (like subtraction or list construction), the results will differ. Thus, they do not always result in the same value v.
• Answer: False (F)

Step 3: Analyze Statement 3

• Statement: In OCaml the entire function body is a single expression.
• Reasoning: OCaml is a functional language where everything is an expression that evaluates to a value. Even sequences of operations joined by ; or let ... in blocks are treated as a single compound expression.
• Answer: True (T)

Step 4: List Benefits of Immutability

• Reasoning: Immutability means data structures cannot be modified after creation. This provides several advantages in functional programming:

1. Thread Safety / Concurrency: Since data cannot be modified, there are no race conditions or synchronization issues when multiple threads access the same data.
2. Referential Transparency / Easier Reasoning: Functions are pure and free of side effects, making code much easier to debug, test, and reason about mathematically.
3. Safe Data Sharing: Different parts of a program can share references to the same list without worrying that one part will unexpectedly modify the data for another.

---

Problem 2: OCaml Typing and Evaluating

Step 5: Analyze 2(a) - Type of foo

• Code:

  let rec foo lst =
    match lst with
    | h1::h2::t -> h2 :: h1 :: foo t
    | _ -> lst;;

• Reasoning:
• The function takes a list lst of type 'a list.
• In the pattern h1::h2::t, h1 and h2 are elements of type 'a, and t is a list of type 'a list.
• The output expression h2 :: h1 :: foo t constructs a list by prepending elements of type 'a to the result of foo t. This means the return type of foo is also 'a list.
• Therefore, the type of foo is a function that takes an 'a list and returns an 'a list.
• Type: 'a list -> 'a list

Step 6: Analyze 2(a) - Evaluation of foo [1;2;3;4;5]

• Reasoning:
• foo [1; 2; 3; 4; 5] matches h1::h2::t where h1 = 1, h2 = 2, and t = [3; 4; 5].
• Evaluates to: 2 :: 1 :: foo [3; 4; 5]
• foo [3; 4; 5] matches h1::h2::t where h1 = 3, h2 = 4, and t = [5].
• Evaluates to: 4 :: 3 :: foo [5]
• foo [5] matches the wildcard pattern _ because it has fewer than 2 elements.
• Evaluates to: [5]
• Combining the steps: 2 :: 1 :: 4 :: 3 :: [5] which evaluates to [2; 1; 4; 3; 5].
• Evaluation: [2; 1; 4; 3; 5]

Step 7: Analyze 2(b) - Type of foo

• Code:

Answer:

Problem 1: Basics

1. True (T)
2. False (F)
3. True (T)
4. Benefits of Immutability (Any 2 of the following):

• Thread Safety: Eliminates race conditions in concurrent/multithreaded environments because data cannot be modified.
• Referential Transparency: Makes code easier to reason about, test, and debug because functions have no side effects.
• Safe Data Sharing: Allows data structures to be shared across different parts of a program without risk of accidental modification.

---

Problem 2: OCaml Typing and Evaluating

(a)

• Type of foo: 'a list -> 'a list
• Evaluation: [2; 1; 4; 3; 5]

(b)

• Type of foo: ('a -> 'a) -> 'a -> 'a
• Evaluation: [1]