Note this is a variant created generated from CS1: Intro to Programming 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:

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):

let crew = ["Kirk"; "Spock"; "Uhura"; "McCoy"]

Pattern matching on lists:

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!".

val countdown : int -> unit

Expected output for countdown 5:

5
4
3
2
1
Engage!

Solution:

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: ".

val format_roster : string list -> string list

Example:

# format_roster ["Spock"; "Uhura"; "Sulu"; "Chekov"];;
- : string list =
  ["Officer: Spock"; "Officer: Uhura"; "Officer: Sulu"; "Officer: Chekov"]

Solution:

let format_roster names =
  List.map (fun name -> "Officer: " ^ name) names

To print the roster to the console:

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.

val red_alert_sectors : (string * int) list -> int -> (string * int) list

Example:

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:

let red_alert_sectors scans threshold =
  List.filter (fun (_, level) -> level > threshold) scans

To display the results:

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.

val total_energy : float list -> float

Then write a second function that returns the average reading.

val average_energy : float list -> float

Example:

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:

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.

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.

val tribble_timeline : int -> int -> int list

Example:

# tribble_population 1 10;;
- : int = 1024

# tribble_timeline 1 5;;
- : int list = [1; 2; 4; 8; 16; 32]

Solution:

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:

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.

type command =
  | Warp of int
  | Shields of bool
  | Scan of string
  | Hail of string

val execute_commands : command list -> unit

Example:

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:

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.