This OCaml code defines and implements insertion into a Binary Search Tree (BST) using a recursive approach. A BST is a data structure where each node has at most two children, referred to as the left child and the right...

The provided OCaml code implements recursive insertion into a Binary Search Tree (BST). The `bst_node` type is defined as either `Empty` or a `Node` containing a value and two child BSTs. The `insert` function takes a value and a tree, returning a new tree with the value inserted. The base case for the recursion is when the tree is `Empty`; in this scenario, a new `Node` is created with the given value and two `Empty` children. For a non-empty `Node`, the function compares the `value` to be inserted with the `node_value`. If `value` is smaller, it recursively calls `insert` on the `left` subtree. If `value` is larger, it recursively calls `insert` on the `right` subtree. If `value` is equal to `node_value`, the tree remains unchanged to ensure unique values. The `create_node` helper constructs a new node, ensuring immutability by returning a new tree structure rather than modifying existing nodes. The time complexity for insertion in a balanced BST is O(log n), where n is the number of nodes. However, in the worst case (a skewed tree), it can degrade to O(n). The space complexity is O(log n) for a balanced tree due to the recursion stack, and O(n) for a skewed tree. Edge cases like inserting into an empty tree, inserting smaller/larger values than existing ones, and handling duplicates are addressed.

type bst_node: Empty Node(value, left_child, right_child) function insert(value, tree): if tree is Empty: return Node(value, Empty, Empty) else: node_value = tree.value left_child = tree.left_child right_child = tree.rig...

This OCaml code implements a Depth-First Search (DFS) algorithm to detect cycles in a directed graph. The graph is represented immutably using an adjacency list (a Hashtbl mapping node IDs to lists of neighbor IDs). The...

The `dfs` function performs the core traversal. It marks a node as `Visiting` upon entry. For each neighbor, it checks its state: if `Visiting`, a cycle is found. If `Unvisited` (or not yet in the `visited_states` map, implying `Unvisited`), it recursively calls `dfs`. If a neighbor is `Visited`, it's ignored. Upon returning from all neighbor explorations, the node is marked `Visited`. The `has_cycle` function iterates through all nodes, initiating DFS from any `Unvisited` node to handle disconnected components. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) for storing the `visited_states` and the recursion stack. Edge cases include empty graphs, graphs with no edges, and graphs with multiple disconnected components.

function has_cycle(graph): visited_states = map of node -> state (Unvisited, Visiting, Visited) initialize all nodes in graph to Unvisited for each node in graph: if node is Unvisited: if dfs(graph, node, visited_states)...

This OCaml code implements a recursive descent parser for arithmetic expressions. It first tokenizes the input string using a simple lexer, then constructs an abstract syntax tree (AST) representing the expression. This...

The parser uses a top-down, recursive descent approach. The `parse_expr` function initiates the parsing process, delegating to `parse_add_sub` to handle addition and subtraction, which have lower precedence. `parse_add_sub` in turn calls `parse_mul_div` for multiplication and division, and `parse_mul_div` calls `parse_atom` for the most basic elements like numbers and parenthesized sub-expressions. This structure naturally enforces operator precedence. Associativity is handled by the recursive calls within `parse_add_sub_cont` and `parse_mul_div_cont`, which allow for sequences of the same-precedence operators. Error handling is included for malformed input, such as mismatched parentheses or unexpected tokens. The time complexity is O(N) where N is the number of tokens, as each token is processed a constant number of times. The space complexity is O(N) in the worst case due to the recursion depth and the AST construction.

function parse(tokens): result, remaining = parse_expression(tokens) if remaining contains only EOF: return result else: raise ParseError("Unexpected tokens") function parse_expression(tokens): left, tokens' = parse_add_...

This OCaml code defines a state machine for a simple vending machine using algebraic data types and pattern matching. The machine has states like 'Idle', 'HasCoin', and 'Dispensing', and transitions based on inputs like...

The state machine is implemented using OCaml's powerful pattern matching on algebraic data types. The `state` type enumerates all possible configurations of the machine, and the `input` type defines all valid user interactions. The `process_input` function is the core transition logic: it takes the current state and an input, and returns the next state. Each `match` clause covers a specific `(current_state, input)` combination, defining the resulting state and any side effects (though this example focuses purely on state transitions). The use of `HasCoin of coin_value` and `Dispensing of product_id * coin_value` allows the state itself to carry context. The `simulate_vending_machine` function applies a list of inputs sequentially. The time complexity is O(N) where N is the number of inputs, as each input is processed in constant time. Space complexity is O(1) for the state itself, plus O(N) for the input list. Edge cases include invalid coin amounts, insufficient funds, and invalid product selections, all handled by specific pattern matches.

define state = Idle | HasCoin(amount) | Dispensing(product, change) define input = InsertCoin(amount) | SelectProduct(product_id) | Cancel function process_input(current_state, input): case (current_state, input) of: (Id...

This OCaml code implements Breadth-First Search (BFS) to find the shortest path in an unweighted directed graph. The graph is represented using an adjacency list. BFS explores the graph level by level, guaranteeing that...

The `shortest_path` function initializes a queue, a `distances` map (all nodes to -1, source to 0), and a `predecessors` map. The BFS loop dequeues a node, explores its unvisited neighbors, updates their distances (current_dist + 1), records their predecessor, and enqueues them. This process continues until the queue is empty. If the target's distance is still -1, it's unreachable. Otherwise, the path is reconstructed by backtracking from the target using the `predecessors` map. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is processed at most once. The space complexity is O(V) for the queue, distances, and predecessors. Edge cases include the source and target being the same, the target being unreachable, and the source or target not existing in the graph.

function shortest_path(graph, source, target): queue = empty queue distances = map of node -> distance (initialize all to -1) predecessors = map of node -> predecessor if source not in graph or target not in graph: retur...

This OCaml code implements a parser for a simple configuration file DSL using a combinator-style approach. It defines parsers for basic elements like keys, values, and section headers, and combines them to parse the over...

The parser is built using a set of primitive parsers (e.g., `literal`, `take_while`, `char`) and combinators (`seq`, `choice`, `many`, `many1`) that build more complex parsers. Each parser takes an input string and returns a `result` type: either `Ok (parsed_value, remaining_input)` or `Error error_details`. The `error` type includes specific messages like `UnexpectedToken` and `UnexpectedEOF`, aiding in debugging. The `parse_config` function orchestrates the parsing of sections and key-value pairs. The `skip_whitespace` parser is used throughout to ignore irrelevant characters. The time complexity is roughly O(N*M) in the worst case for naive combinators, where N is the input length and M is the number of parsers, but with optimizations and careful design, it approaches O(N). Space complexity is O(N) for intermediate string manipulations and the resulting AST. Edge cases include empty input, malformed keys/values, missing delimiters, and incorrect section nesting.

define result = Ok(value, remaining_input) | Error(error_details) define error = UnexpectedToken(expected, got) | UnexpectedEOF(expected) | CustomError(message) define parser = input_string -> result // Primitive parsers...