3 OCaml Exercises
3.1 Problem 1: Basics (Spring 2025 Quiz 1)
Using mutable variables can cause side effects.
Using mutable variables can cause side effects.
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.
Due to OCaml’s type constraints, you cannot make a list of functions.
Due to OCaml’s type constraints, you cannot make a list of functions.
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.
fold_left’s accumulator can be a list.
fold_left’s accumulator can be a list.
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.
fold_left’s accumulator can be a tuple.
fold_left’s accumulator can be a tuple.
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.
3.2 Problem 1: Basics (Spring 2024 Quiz 1)
OCaml uses type inference to determine the type of variables.
OCaml uses type inference to determine the type of variables.
Answer: True. OCaml has a powerful type inference system that automatically determines the types of expressions without requiring explicit type annotations.
Functional Programming Languages favor mutable data.
Functional Programming Languages favor mutable data.
Answer: False. Functional programming languages favor immutable data. Immutability helps avoid side effects and makes programs easier to reason about.
Functional Programming aims to decrease the amount of side effects.
Functional Programming aims to decrease the amount of side effects.
Answer: True. A core goal of functional programming is to minimize side effects by using pure functions and immutable data.
Functions are expressions in OCaml.
Functions are expressions in OCaml.
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.
3.3 Problem 1: Basics (Fall 2024 Quiz)
In OCaml, all values are expressions but not all expressions are values.
In OCaml, all values are expressions but not all expressions are values.
Answer: True. Everything is an expression, but 2 + 3 is an expression that is not a value —
map (fun x -> x + 1) a will modify the list a in-place.
map (fun x -> x + 1) a will modify the list a in-place.
Answer: False. map doesn’t modify anything in place because lists are immutable in OCaml. It returns a new list.
Having mutable variables can make it hard to reason about how a program runs.
Having mutable variables can make it hard to reason about how a program runs.
Answer: True. Side effects occur when we have mutability, which can make it difficult to reason about program behavior.
A function with type int -> float -> bool returns 2 things: a float and a bool.
A function with type int -> float -> bool returns 2 things: a float and a bool.
Answer: False. Functions return only 1 thing. This function takes an int and a float and returns a bool.
A function with type int -> bool -> float could be interpreted as returning a bool -> float function.
A function with type int -> bool -> float could be interpreted as returning a bool -> float function.
Answer: True. Currying allows for this interpretation. int -> bool -> float is equivalent to int -> (bool -> float).
let f x = x + 3 is an example of a higher order function.
let f x = x + 3 is an example of a higher order function.
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.
let f x = x 3 is an example of a higher order function.
let f x = x 3 is an example of 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.
An OCaml function can return different types depending on how it’s called.
An OCaml function can return different types depending on how it’s called.
Answer: False. A function can only return 1 type (or 1 polymorphic type). The return type is fixed at definition time.
let x = 3 in let x = 4 in x is an example of variable shadowing.
let x = 3 in let x = 4 in x is an example of variable shadowing.
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.
let x = 3 in let y = 4 in y + x is an example of variable shadowing.
let x = 3 in let y = 4 in y + x is an example of variable shadowing.
Answer: False. There are no two variables with the same name, so no shadowing occurs.
3.4 Problem 1: Basics
List.length x = (List.length (List.map f x)) for all valid f and x (i.e., assume List.map f x compiles).
List.length x = (List.length (List.map f x)) for all valid f and x (i.e., assume List.map f x compiles).
Answer: True. List.map f x always produces a list of the same length as x, regardless of what f does to each element.
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.
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.
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.
In OCaml the entire function body is a single expression.
In OCaml the entire function body is a single expression.
Answer: True. In OCaml, a function body is always a single expression. There are no statements —
OCaml lists are immutable. List 2 benefits of immutability in functional programming.
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.
3.5 Problem 2: OCaml Typing and Evaluating (Spring 2025 Quiz 1)
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y =
match x,y with
x::xs,y::ys -> y :: xs
| _ -> [] ;;
foo [] [1;2;3] ;;
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y =
match x,y with
x::xs,y::ys -> y :: xs
| _ -> [] ;;
foo [] [1;2;3] ;;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 [].
What is the type of foo and what does foo [3;6;9] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot + ele * idx, idx + 1))
(0, 0)
lst in total;;
foo [3;6;9] ;;
What is the type of foo and what does foo [3;6;9] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot + ele * idx, idx + 1))
(0, 0)
lst in total;;
foo [3;6;9] ;;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.
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y =
match x,y with
x::xs,y::ys -> y :: xs
| _ -> (0,0) ;;
foo [] [1;2;3] ;;
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y =
match x,y with
x::xs,y::ys -> y :: xs
| _ -> (0,0) ;;
foo [] [1;2;3] ;;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.
What is the type of foo and what does foo [7;4;23] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot*ele*idx, idx + 1))
(0, 0)
lst in total;;
foo [7;4;23] ;;
What is the type of foo and what does foo [7;4;23] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot*ele*idx, idx + 1))
(0, 0)
lst in total;;
foo [7;4;23] ;;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.
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y = match x,y with
x::xs,y::ys -> y :: xs
| _ -> [9] ;;
foo [] [1;2;3] ;;
What is the type of foo and what does foo [] [1;2;3] evaluate to?
let foo x y = match x,y with
x::xs,y::ys -> y :: xs
| _ -> [9] ;;
foo [] [1;2;3] ;;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].
What is the type of foo and what does foo [2;4;8] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot + ele * idx, idx + 1))
(0, 0)
lst in total;;
foo [2;4;8] ;;
What is the type of foo and what does foo [2;4;8] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot + ele * idx, idx + 1))
(0, 0)
lst in total;;
foo [2;4;8] ;;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.
What is the type of foo and what does foo (1,3) [1;2;3] evaluate to?
let foo x y = match x,y with
x::xs,y::ys -> y :: xs
| _ -> [] ;;
foo (1,3) [1;2;3] ;;
What is the type of foo and what does foo (1,3) [1;2;3] evaluate to?
let foo x y = match x,y with
x::xs,y::ys -> y :: xs
| _ -> [] ;;
foo (1,3) [1;2;3] ;;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.
What is the type of foo and what does foo [1;3;5] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot * ele * idx, idx + 1))
(1, 0)
lst in total;;
foo [1;3;5] ;;
What is the type of foo and what does foo [1;3;5] evaluate to?
let foo lst = let total, _ =
fold_left
(fun (tot, idx) ele ->
(tot * ele * idx, idx + 1))
(1, 0)
lst in total;;
foo [1;3;5] ;;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.
3.6 Problem 2: OCaml Typing (Spring 2024 Quiz 1)
What is the type of f and what does f [4] [[6]] evaluate to?
let f x y = match x with
[] -> y
|x::xs -> [x]::[] ;;
f [4] [[6]] ;;
What is the type of f and what does f [4] [[6]] evaluate to?
let f x y = match x with
[] -> y
|x::xs -> [x]::[] ;;
f [4] [[6]] ;;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]].
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > a then b
else a < true ;;
f 2.0 false;;
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > a then b
else a < true ;;
f 2.0 false;;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 —
What is the type of f and what does f [4] evaluate to?
let f x = match x with
[] -> [[3]]
|x::xs -> [x]::[] ;;
f [4];;
What is the type of f and what does f [4] evaluate to?
let f x = match x with
[] -> [[3]]
|x::xs -> [x]::[] ;;
f [4];;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]].
What is the type of f and what does f true false (fun x y -> x > y) evaluate to?
let f a b c =
if b > a then c
else a < true ;;
f true false (fun x y -> x > y);;
What is the type of f and what does f true false (fun x y -> x > y) evaluate to?
let f a b c =
if b > a then c
else a < true ;;
f true false (fun x y -> x > y);;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 —
What is the type of f and what does f [4] [[6]] evaluate to?
let f x y = match x with
[] -> y
|_::xs -> [2]::[]
|4::xs -> [4]::[];;
f [4] [[6]] ;;
What is the type of f and what does f [4] [[6]] evaluate to?
let f x y = match x with
[] -> y
|_::xs -> [2]::[]
|4::xs -> [4]::[];;
f [4] [[6]] ;;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]].
What is the type of f and what does f true 1.3 evaluate to?
let f a b =
if b > a then (1.3 < 4.6)
else a < true ;;
f true 1.3;;
What is the type of f and what does f true 1.3 evaluate to?
let f a b =
if b > a then (1.3 < 4.6)
else a < true ;;
f true 1.3;;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 —
What is the type of f and what does f [(1,2);(3,4)] [[(6,7)]] evaluate to?
let f x y = match x with
[] -> y
|x::xs -> [x]::[] ;;
f [(1,2);(3,4)] [[(6,7)]] ;;
What is the type of f and what does f [(1,2);(3,4)] [[(6,7)]] evaluate to?
let f x y = match x with
[] -> y
|x::xs -> [x]::[] ;;
f [(1,2);(3,4)] [[(6,7)]] ;;Answer: Type is ’a list -> ’a list list -> ’a list list. Same function as (a) —
What is the type of f and what does f (fun x -> x < 1) false evaluate to?
let f a b =
if b > a then ("hello" < "bye")
else a < true ;;
f (fun x -> x < 1) false;;
What is the type of f and what does f (fun x -> x < 1) false evaluate to?
let f a b =
if b > a then ("hello" < "bye")
else a < true ;;
f (fun x -> x < 1) false;;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 —
3.7 Problem 2: OCaml Typing and Evaluating (Fall 2024 Quiz)
What is the type of f and what does f [] [1;2;3] evaluate to?
let f x y = match x with
[] -> []
|x::xs -> y :: xs ;;
f [] [1;2;3] ;;
What is the type of f and what does f [] [1;2;3] evaluate to?
let f x y = match x with
[] -> []
|x::xs -> y :: xs ;;
f [] [1;2;3] ;;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 [].
What is the type of f and what does f [] [1;2;3] evaluate to?
let f x y = match x with
[] -> [1]
|x::xs -> y :: xs ;;
f [] [1;2;3] ;;
What is the type of f and what does f [] [1;2;3] evaluate to?
let f x y = match x with
[] -> [1]
|x::xs -> y :: xs ;;
f [] [1;2;3] ;;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 —
What is the type of f and what does f [1] [1;2;3] evaluate to?
let f x y = match x with
[] -> [14]
|x::xs -> y :: xs ;;
f [1] [1;2;3] ;;
What is the type of f and what does f [1] [1;2;3] evaluate to?
let f x y = match x with
[] -> [14]
|x::xs -> y :: xs ;;
f [1] [1;2;3] ;;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.
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b <> false then 1.0
else a + 2.0 ;;
f 2.0 false;;
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b <> false then 1.0
else a + 2.0 ;;
f 2.0 false;;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.
What is the type of f and what does f 2 "true" evaluate to?
let f a b =
if b = "false" then 1
else a + 2 ;;
f 2 "true";;
What is the type of f and what does f 2 "true" evaluate to?
let f a b =
if b = "false" then 1
else a + 2 ;;
f 2 "true";;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.
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > 5 then a
else true ;;
f 2.0 false;;
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > 5 then a
else true ;;
f 2.0 false;;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 —
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > false then a
else 2.3 ;;
f 2.0 false;;
What is the type of f and what does f 2.0 false evaluate to?
let f a b =
if b > false then a
else 2.3 ;;
f 2.0 false;;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.
What is the type of f and what does f (fun x -> x mod 2 = 1) [1;2;3] evaluate to?
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] ;;
What is the type of f and what does f (fun x -> x mod 2 = 1) [1;2;3] evaluate to?
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] ;;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.
What is the type of f and what does f (fun x -> x mod 2 = 0) [1;2;3] evaluate to?
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] ;;
What is the type of f and what does f (fun x -> x mod 2 = 0) [1;2;3] evaluate to?
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] ;;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.
What is the type of f and what does f (fun x -> x +. 2.0) [1.0;2.0;3.0] evaluate to?
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];;
What is the type of f and what does f (fun x -> x +. 2.0) [1.0;2.0;3.0] evaluate to?
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];;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.
What is the type of f and what does f (fun x -> x *. 2.0) [1.0;2.0;3.0] evaluate to?
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];;
What is the type of f and what does f (fun x -> x *. 2.0) [1.0;2.0;3.0] evaluate to?
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];;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.
3.8 Problem 2: OCaml Typing and Evaluating
What is the type of foo and what does foo [1;2;3;4;5] evaluate to?
let rec foo lst =
match lst with
h1::h2::t -> h2 :: h1 :: foo t
| _ -> lst;;
foo [1;2;3;4;5];;
What is the type of foo and what does foo [1;2;3;4;5] evaluate to?
let rec foo lst =
match lst with
h1::h2::t -> h2 :: h1 :: foo t
| _ -> lst;;
foo [1;2;3;4;5];;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.
What is the type of foo and what does the call evaluate to?
let foo f x = f (f x);;
foo (fun x -> [List.length x]) [3;6;9];;
What is the type of foo and what does the call evaluate to?
let foo f x = f (f x);;
foo (fun x -> [List.length x]) [3;6;9];;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].
3.9 Problem 3: Coding
Define a function fold_if that behaves like fold_left,
but takes an additional predicate argument pred : ’acc -> ’a -> bool.
During the fold, before applying the function to the current element,
pred is checked with the current accumulator and the current element.
If pred evaluates to false, the fold stops
and returns the current accumulator.
(* stop when we encounter an element > 10 *)
let pred _acc x = x <= 10 in
let f acc x = acc + x in
fold_if pred f 0 [1;4;6;11;2]
(* returns 11 (1+4+6), stops at 11 *)
(* stop once acc >= 10 *)
let pred_sum acc _x = acc < 10 in
let f acc x = acc + x in fold_if pred_sum f 0 [3;4;5;1]
(* returns 12 (3+4+5), stops before processing 1 *)
Define a function fold_if that behaves like fold_left, but takes an additional predicate argument pred : ’acc -> ’a -> bool. During the fold, before applying the function to the current element, pred is checked with the current accumulator and the current element. If pred evaluates to false, the fold stops and returns the current accumulator.
(* stop when we encounter an element > 10 *)
let pred _acc x = x <= 10 in
let f acc x = acc + x in
fold_if pred f 0 [1;4;6;11;2]
(* returns 11 (1+4+6), stops at 11 *)
(* stop once acc >= 10 *)
let pred_sum acc _x = acc < 10 in
let f acc x = acc + x in fold_if pred_sum f 0 [3;4;5;1]
(* returns 12 (3+4+5), stops before processing 1 *)let rec fold_if pred f init lst =
match lst with
| [] -> init
| x :: xs ->
if pred init x then fold_if pred f (f init x) xs
else init3.10 Problem 3: Filter (Spring 2025 Quiz 1)
filter is a common higher order function that has type (’a -> bool) -> ’a list -> ’a list. It applies
a function to every item in a list and returns a list of the items that caused the function to return true. Using only fold
(left or right), write a function called my_filter which has the same functionality as filter. f will be the
function that returns true or false, and l will be the list. Note: the original order must be maintained.
(* example: my_filter (fun x -> x > 3) [2;4;6] = [4;6] *)
filter is a common higher order function that has type (’a -> bool) -> ’a list -> ’a list. It applies a function to every item in a list and returns a list of the items that caused the function to return true. Using only fold (left or right), write a function called my_filter which has the same functionality as filter. f will be the function that returns true or false, and l will be the list. Note: the original order must be maintained.
(* example: my_filter (fun x -> x > 3) [2;4;6] = [4;6] *)(* Using fold_right *)
let my_filter f l =
fold_right (fun x acc -> if f x then x :: acc else acc) l []
(* Alternatively, using fold_left *)
let my_filter f l =
fold_left (fun acc x -> if f x then acc @ [x] else acc) [] l3.11 Problem 4: Coding (Spring 2025 Quiz 1)
Write a function last_sum which takes in a int list list and returns the sum of the last elements in each int list. If a list is empty, it adds nothing to the total.
(* last_sum has type int list list -> int *)
(* Examples:
last_sum [] = 0
last_sum [[1;2;3];[4;5;6];[7;8;9]] = 18 (* 3 + 6 + 9 *)
last_sum [[];[1];[2;3]] = 4 (* 0 + 1 + 3 *)
*)
Write a function last_sum which takes in a int list list and returns the sum of the last elements in each int list. If a list is empty, it adds nothing to the total.
(* last_sum has type int list list -> int *)
(* Examples:
last_sum [] = 0
last_sum [[1;2;3];[4;5;6];[7;8;9]] = 18 (* 3 + 6 + 9 *)
last_sum [[];[1];[2;3]] = 4 (* 0 + 1 + 3 *)
*)(* Using map and fold_left *)
let rec last_sum mtx =
let lasts = map (fun x -> fold_left (fun acc el -> el) 0 x) mtx in
fold_left (+) 0 lasts
(* Alternatively, using only fold_left *)
let last_sum mtx =
fold_left (fun a x -> a + (fold_left (fun a x -> x) 0 x)) 0 mtx
(* Alternatively, with a helper function *)
let rec get_last lst = match lst with
| [] -> 0
| [x] -> x
| _ :: xs -> get_last xs
let rec last_sum mtx =
let lasts = map (fun x -> get_last x) mtx in
fold_left (+) 0 lastsWrite a function last_prod which takes in a int list list and returns the product of the last elements in each int list. If a list is empty, it multiplies the value by 1.
(* last_prod has type int list list -> int *)
(* Examples:
last_prod [] = 1
last_prod [[1;2;3];[4;5;6];[7;8;9]] = 162 (* 3 * 6 * 9 *)
last_prod [[];[1];[2;3]] = 3 (* 1 * 1 * 3 *)
*)
Write a function last_prod which takes in a int list list and returns the product of the last elements in each int list. If a list is empty, it multiplies the value by 1.
(* last_prod has type int list list -> int *)
(* Examples:
last_prod [] = 1
last_prod [[1;2;3];[4;5;6];[7;8;9]] = 162 (* 3 * 6 * 9 *)
last_prod [[];[1];[2;3]] = 3 (* 1 * 1 * 3 *)
*)(* Using map and fold_left *)
let rec last_prod mtx =
let lasts = map (fun x -> fold_left (fun acc el -> el) 1 x) mtx in
fold_left ( * ) 1 lasts
(* Alternatively, using only fold_left *)
let last_prod mtx =
fold_left (fun a x -> a * (fold_left (fun a x -> x) 1 x)) 1 mtx
(* Alternatively, with a helper function *)
let rec get_last lst = match lst with
| [] -> 1
| [x] -> x
| _ :: xs -> get_last xs
let rec last_prod mtx =
let lasts = map (fun x -> get_last x) mtx in
fold_left ( * ) 1 lastsWrite a function last_concat which takes in a string list list and returns the result of concatenating the last elements in each string list. If a list is empty, it should not modify the resulting string.
(* last_concat has type string list list -> string *)
(* Examples:
last_concat [] = ""
last_concat [["a";"b"];["c";"d"];["e";"f"]] = "bdf"
last_concat [[];["a"];["b";"c"]] = "ac"
*)
Write a function last_concat which takes in a string list list and returns the result of concatenating the last elements in each string list. If a list is empty, it should not modify the resulting string.
(* last_concat has type string list list -> string *)
(* Examples:
last_concat [] = ""
last_concat [["a";"b"];["c";"d"];["e";"f"]] = "bdf"
last_concat [[];["a"];["b";"c"]] = "ac"
*)(* Using map and fold_right *)
let rec last_concat mtx =
let lasts = map (fun x -> fold_left (fun acc el -> el) "" x) mtx in
fold_right ( ^ ) lasts ""
(* Alternatively, with a helper function *)
let rec get_last lst = match lst with
| [] -> ""
| [x] -> x
| _ :: xs -> get_last xs
let last_concat mtx =
let lasts = map (fun x -> get_last x) mtx in
fold_right ( ^ ) lasts ""3.12 Problem 3: OCaml Expressions (Spring 2024 Quiz 1)
Write an expression that would have the type int list -> ’a -> ’a -> bool.
Write an expression that would have the type int list -> ’a -> ’a -> bool.
fun x y z -> match x with
|h::t -> (if h = 0 then y = z else false)
|[] -> trueWrite an expression that would have the type (int -> ’a) -> int -> int * ’a list.
Write an expression that would have the type (int -> ’a) -> int -> int * ’a list.
fun f a -> (a + 1, [f a])Write an expression that would have the type (’a -> ’b) -> ’a -> ’b -> bool.
Write an expression that would have the type (’a -> ’b) -> ’a -> ’b -> bool.
fun x y z -> (x y) = zWrite an expression that would have the type float -> float -> bool -> float list.
Write an expression that would have the type float -> float -> bool -> float list.
fun x y z -> if z then [x +. 1.0] else [y]Write an expression that would have the type (int * ’a) -> (bool -> ’a) -> ’a.
Write an expression that would have the type (int * ’a) -> (bool -> ’a) -> ’a.
fun (a, b) c -> if a + 1 = 2 then b else c trueWrite an expression that would have the type int list -> int -> bool list.
Write an expression that would have the type int list -> int -> bool list.
fun x y -> match x with
|h::t -> [h + 1 = y]
|[] -> [false]Write an expression that would have the type ’a -> ’b list -> ’a -> ’a * ’a.
Write an expression that would have the type ’a -> ’b list -> ’a -> ’a * ’a.
fun x y z -> if y = [] && x = z then (x, z) else (x, z)3.13 Problem 3: OCaml Expressions (Fall 2024 Quiz)
Write an expression that would have the type ’a -> ’a -> bool list.
Write an expression that would have the type ’a -> ’a -> bool list.
fun a b -> [a = b]Write an expression that would have the type (’a -> ’a) -> ’a -> int.
Write an expression that would have the type (’a -> ’a) -> ’a -> int.
fun f a -> if (f a) = a then 3 else 5Write an expression that would have the type float -> ’a -> (’a * float).
Write an expression that would have the type float -> ’a -> (’a * float).
fun a b -> (b, a +. 2.)Write an expression that would have the type string -> ’a -> (’a * float * ’a).
Write an expression that would have the type string -> ’a -> (’a * float * ’a).
fun s a -> (a, (float_of_string s), a)Write an expression that would have the type bool -> int -> (bool * int) list.
Write an expression that would have the type bool -> int -> (bool * int) list.
fun b i -> [b > true, i + 3]Write an expression that would have the type (int -> ’a) -> ’b -> ’a.
Write an expression that would have the type (int -> ’a) -> ’b -> ’a.
fun f a -> f 3Write an expression that would have the type (’a -> ’b) -> ’a -> ’b.
Write an expression that would have the type (’a -> ’b) -> ’a -> ’b.
fun f b -> f bWrite an expression that would have the type (’a -> ’b -> ’c) -> ’a -> ’b -> ’c.
Write an expression that would have the type (’a -> ’b -> ’c) -> ’a -> ’b -> ’c.
fun f a b -> f a b3.14 Problem 4: Coding (Fall 2024 Quiz)
Write a function encode that takes a int list and returns a string list, which consists of the string "1" repeated by each number in the int list. You may assume that all values in the input list are >= 0.
(* Examples:
encode [0;1;2;3] = ["";"1";"11";"111"]
encode [0;0;3] = ["";"";"111"]
*)
Write a function encode that takes a int list and returns a string list, which consists of the string "1" repeated by each number in the int list. You may assume that all values in the input list are >= 0.
(* Examples:
encode [0;1;2;3] = ["";"1";"11";"111"]
encode [0;0;3] = ["";"";"111"]
*)let rec encode lst =
let rec repeat n =
if n = 0 then ""
else "1" ^ repeat (n - 1) in
map repeat lst3.15 Problem 4: Coding (Spring 2024 Quiz 1)
Write a function calc that takes a (int * bool) list and returns a (int * bool), which consists of the sum of the ints and the result of AND’ing the bools.
(* Examples:
calc [(1,true); (2,false)] = (3,false)
calc [(3,true); (4,true)] = (7,true)
*)
Write a function calc that takes a (int * bool) list and returns a (int * bool), which consists of the sum of the ints and the result of AND’ing the bools.
(* Examples:
calc [(1,true); (2,false)] = (3,false)
calc [(3,true); (4,true)] = (7,true)
*)(* Recursive version *)
let rec calc lst = match lst with
| [] -> (0, true)
| (i, b) :: xs ->
let (s, a) = calc xs in (s + i, b && a)
(* Fold version *)
let calc lst =
fold (fun (a, b) (c, d) -> (a + c, b && d)) (0, true) lst