Collections and Records

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/collections-and-records

5. Exercise 3: Collections and Records (~25 min)

File: exercises/collections-and-records/starter/main.ml Run:

dune exec modules/module0-warmup/exercises/collections-and-records/starter/main.exe

What You'll Implement

Function	What It Does	Concept
`double_all`	Doubles each element	List.map
`keep_positive`	Keeps only positive elements	List.filter
`sum`	Sums all elements	List.fold_left
`has_duplicates`	Checks for duplicate strings	Sort + adjacent check
`make_assign`	Creates assignment record	Record construction
`format_assign`	Formats record as string	Record field access
`increment_value`	Creates new record with updated value	`{ a with ... }` syntax
`build_env`	Builds StringMap from pairs	fold + StringMap.add
`lookup_var`	Looks up variable in map	StringMap.find_opt
`all_vars`	Lists all variable names	StringMap.bindings
`assigned_vars`	Collects assigned vars into set	StringSet.add
`common_vars`	Intersects two StringSets	StringSet.inter
`make_counter`	Returns incrementing closure	ref cell

Hints

List.map (fun x -> x * 2) xs applies the function to each element.
List.filter (fun x -> x > 0) xs keeps elements where the function returns true.
List.fold_left (fun acc x -> acc + x) 0 xs accumulates from left with initial value 0.
StringMap.add key value map returns a new map with the binding added.
StringMap.find_opt key map returns Some value or None.
StringMap.bindings map returns a list of (key, value) pairs.
Records: { var_name = "x"; value = 5; line = 1 } and { a with value = 10 }.
ref: let r = ref 0 in r := !r + 1; !r creates, updates, and reads a ref.

Expected Output

=== Exercise 3: Collections and Records ===

double_all [1; 2; 3] = [2; 4; 6]
keep_positive [-1; 3; 0; 5; -2] = [3; 5]
sum [1; 2; 3; 4] = 10
has_duplicates ["a"; "b"; "a"] = true
has_duplicates ["a"; "b"; "c"] = false

format_assign a1 = x = 5 (line 1)
format_assign a2 = y = 10 (line 2)
increment_value a1 3 = x = 8 (line 1)

lookup_var "x" = Some 1
lookup_var "y" = Some 2
lookup_var "w" = None
all_vars env = [x; y; z]

assigned_vars = {x, y}
common_vars = {y, z}

counter: 0, 1, 2

Done!

Note on counter output: OCaml evaluates function arguments in an unspecified order. You might see counter: 2, 1, 0 instead. Both are correct -- what matters is that each call returns a different number.

Starter Files

starter

starter/main.ml

Read-only

Loading editor...

Work on this exercise locally

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/collections-and-records