> Source URL: /demos/lab-demo/ocaml-recursion.lab --- title: Starfleet Recursion Academy source: ./cs1-loops.lab.md outcomes: - Write recursive functions to process lists and accumulate results - Use pattern matching to destructure lists and handle base cases - Apply higher-order functions (map, filter, fold) to transform data - Model simple domains using records and variant types --- > Note this is a variant created generated from [CS1: Intro to Programming](./cs1-loops.lab.md) using `ocaml` rather than Python and use a medium diffuclty level and Star Trek theme. --- # Starfleet Recursion Academy In this lab you'll use OCaml to solve problems aboard the USS Enterprise. Instead of imperative loops, you'll think recursively and harness higher-order functions — the preferred tools of any Starfleet engineer. --- ## Background OCaml programmers rarely reach for `for` or `while`. Instead, repetition is expressed through **recursion** and **higher-order functions** on lists. **Recursion** — a function that calls itself with a smaller problem: ```ocaml let rec countdown n = if n <= 0 then print_endline "Done" else begin Printf.printf "%d\n" n; countdown (n - 1) end ``` **List basics** — lists are built from `[]` (empty) and `::` (cons): ```ocaml let crew = ["Kirk"; "Spock"; "Uhura"; "McCoy"] ``` **Pattern matching** on lists: ```ocaml let rec length lst = match lst with | [] -> 0 | _ :: rest -> 1 + length rest ``` **Key `List` module functions:** | Function | Purpose | | --------------------------- | ------------------------------------------- | | `List.map f lst` | Apply `f` to every element, return new list | | `List.filter f lst` | Keep elements where `f` returns `true` | | `List.fold_left f init lst` | Accumulate a result across the list | | `List.iter f lst` | Apply `f` to every element for side effects | --- ## Exercise 1: Captain's Log (Countdown) The warp drive is spinning up. Write a recursive function `countdown n` that prints a countdown from `n` down to 1, then prints `"Engage!"`. ```ocaml val countdown : int -> unit ``` **Expected output for `countdown 5`:** ``` 5 4 3 2 1 Engage! ``` **Solution:** ```ocaml let rec countdown n = if n <= 0 then print_endline "Engage!" else begin Printf.printf "%d\n" n; countdown (n - 1) end ``` --- ## Exercise 2: Crew Roster (List Mapping) Starfleet Command needs a formatted crew manifest. Given a list of names, use `List.map` to produce a list where each name is prefixed with `"Officer: "`. ```ocaml val format_roster : string list -> string list ``` **Example:** ```ocaml # format_roster ["Spock"; "Uhura"; "Sulu"; "Chekov"];; - : string list = ["Officer: Spock"; "Officer: Uhura"; "Officer: Sulu"; "Officer: Chekov"] ``` **Solution:** ```ocaml let format_roster names = List.map (fun name -> "Officer: " ^ name) names ``` To print the roster to the console: ```ocaml let print_roster names = let formatted = format_roster names in List.iter print_endline formatted ``` --- ## Exercise 3: Red Alert Filter Long-range sensors have detected activity across several sectors. Each scan result is a tuple of `(sector_name, threat_level)`. Write a function that returns only the sectors whose threat level exceeds a given threshold. ```ocaml val red_alert_sectors : (string * int) list -> int -> (string * int) list ``` **Example:** ```ocaml let scans = [ ("Neutral Zone", 9); ("Alpha Quadrant", 2); ("Romulan Border", 7); ("Earth Spacedock", 1); ("Klingon Territory", 8) ] # red_alert_sectors scans 5;; - : (string * int) list = [("Neutral Zone", 9); ("Romulan Border", 7); ("Klingon Territory", 8)] ``` **Solution:** ```ocaml let red_alert_sectors scans threshold = List.filter (fun (_, level) -> level > threshold) scans ``` To display the results: ```ocaml let report_threats scans threshold = let dangerous = red_alert_sectors scans threshold in Printf.printf "Red Alert — %d sector(s) above threat level %d:\n" (List.length dangerous) threshold; List.iter (fun (name, level) -> Printf.printf " %-20s threat level %d\n" name level) dangerous ``` --- ## Exercise 4: Starship Power Calculation (Fold) Engineering reports warp core output readings from the last several hours. Compute the total energy output using `List.fold_left`. ```ocaml val total_energy : float list -> float ``` Then write a second function that returns the **average** reading. ```ocaml val average_energy : float list -> float ``` **Example:** ```ocaml let readings = [42.5; 37.8; 45.1; 39.9; 41.0; 44.3] # total_energy readings;; - : float = 250.6 # average_energy readings;; - : float = 41.7666666666666671 ``` **Solution:** ```ocaml let total_energy readings = List.fold_left ( +. ) 0.0 readings let average_energy readings = let total = total_energy readings in total /. Float.of_int (List.length readings) ``` --- ## Exercise 5: Tribble Population (Recursive Growth) A tribble has been found on the ship. Tribbles double their population every hour. Write a recursive function that computes the population after a given number of hours. ```ocaml val tribble_population : int -> int -> int ``` Then write a variant that returns a **list** of the population at each hour (hour 0 through hour `n`), so the crew can track the infestation. ```ocaml val tribble_timeline : int -> int -> int list ``` **Example:** ```ocaml # tribble_population 1 10;; - : int = 1024 # tribble_timeline 1 5;; - : int list = [1; 2; 4; 8; 16; 32] ``` **Solution:** ```ocaml let rec tribble_population start hours = if hours <= 0 then start else tribble_population (start * 2) (hours - 1) let tribble_timeline start hours = let rec aux current h acc = if h < 0 then List.rev acc else aux (current * 2) (h - 1) (current :: acc) in aux start hours [] ``` To display an infestation report: ```ocaml let infestation_report start hours = let timeline = tribble_timeline start hours in List.iteri (fun i pop -> Printf.printf " Hour %d: %d tribbles\n" i pop) timeline; let final = List.nth timeline (List.length timeline - 1) in if final > 1000 then print_endline " WARNING: Recommend immediate containment!" else print_endline " Status: Situation manageable." ``` --- ## Exercise 6: Ship's Computer (Pattern Matching + Variants) Define a variant type representing bridge commands, then write a function that processes a list of commands and prints the appropriate response for each. ```ocaml type command = | Warp of int | Shields of bool | Scan of string | Hail of string ``` ```ocaml val execute_commands : command list -> unit ``` **Example:** ```ocaml let orders = [ Warp 7; Shields true; Scan "Sector 31"; Hail "Klingon Vessel"; Warp 3; Shields false; ] # execute_commands orders;; ``` **Expected output:** ``` Setting warp factor to 7. Engage! Shields up! Brace for impact. Scanning Sector 31... complete. Opening hailing frequencies to Klingon Vessel. Setting warp factor to 3. Engage! Shields down. Standing by. ``` **Solution:** ```ocaml type command = | Warp of int | Shields of bool | Scan of string | Hail of string let execute_one cmd = match cmd with | Warp n -> Printf.printf "Setting warp factor to %d. Engage!\n" n | Shields up -> if up then print_endline "Shields up! Brace for impact." else print_endline "Shields down. Standing by." | Scan sector -> Printf.printf "Scanning %s... complete.\n" sector | Hail target -> Printf.printf "Opening hailing frequencies to %s.\n" target let execute_commands orders = List.iter execute_one orders ``` --- ## Wrap-Up You practiced: - **Recursion** to replace imperative loops with self-calling functions - **Pattern matching** to destructure lists and variant types - **`List.map`** to transform every element of a list - **`List.filter`** to select elements matching a predicate - **`List.fold_left`** to accumulate a result across a list - **Variant types** to model a small domain and dispatch with pattern matching These are the core patterns of functional programming in OCaml. Master them and you'll be ready for your next mission — whether it's charting unknown space or building real-world software. Live long and recurse. --- ## Backlinks The following sources link to this document: - [Starfleet Recursion Academy (OCaml Lab)](/index.path.llm.md)