This Haskell function `isPalindrome` determines if a given string reads the same forwards and backward. It employs a recursive approach, comparing the first and last characters of the string. If they match, it recursivel...

The `isPalindrome` function checks for palindromes using recursion. The base cases are an empty string or a single-character string, both of which are considered palindromes and return `True`. For longer strings, it compares the `head` (first character) with the `last` character. If they are equal, it recursively calls `isPalindrome` on the string excluding the first and last characters (`init (tail str)`). If the `head` and `last` characters differ, the string is not a palindrome, and it returns `False`. This recursive structure effectively shrinks the problem space with each call. The time complexity is O(N), where N is the length of the string, because each character is examined at most once. The space complexity is O(N) in the worst case due to the recursion depth, which can be optimized to O(1) with tail-call optimization or an iterative approach if needed, though Haskell's compiler is good at optimizing this. Edge cases like empty strings and single-character strings are handled explicitly.

function isPalindrome(str): if length of str is 0 or 1: return true firstChar = first character of str lastChar = last character of str if firstChar is equal to lastChar: return isPalindrome(substring of str excluding fi...

This Haskell code implements Breadth-First Search (BFS) to find the shortest path in an unweighted graph. BFS systematically explores the graph level by level, guaranteeing that the first time the target node is reached,...

The `shortestPathBFS` function initializes the BFS process by setting up a queue with the starting node, a set to track visited nodes, and a map to store the predecessor of each visited node. The `bfs` helper function iteratively dequeues a node, explores its unvisited neighbors, enqueues them, and updates their predecessors in the path map. This continues until the queue is empty or the target node is found. The `processNeighbor` function handles the logic for adding a new node to the queue and marking it as visited. Finally, `reconstructPath` traces back from the target node using the path map to build the shortest path. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited at most once. The space complexity is also O(V + E) in the worst case for storing the queue, visited set, and path map. Edge cases like disconnected graphs, unreachable targets, and start/end nodes not being in the graph are handled by returning `Nothing`.

function shortestPathBFS(graph, startNode, endNode): if startNode or endNode not in graph: return null if startNode == endNode: return [startNode] queue = new Queue() visited = new Set() pathMap = new Map() enqueue start...

This Haskell code implements memoization for the factorial function, a common technique for functional caching. It uses a global `IORef` holding a `Map` to store previously computed results. When `factorialMemoized` is c...

The `factorialMemoized` function computes factorials while using a cache. It first checks for base cases (`n < 0` or `n == 0`). If `n` is positive, it looks up `n` in the `globalCacheFactorial`. If found, the cached `result` is returned. If not found, the factorial is computed recursively (`fromIntegral n * factorialMemoized (n - 1)`), the `result` is inserted into the cache using `writeIORef`, and then returned. The use of `unsafePerformIO` and `{-# NOINLINE #-}` is a common (though potentially dangerous) pattern to create a global mutable cache that appears pure from the outside. For pure functional caching without `unsafePerformIO`, one would typically pass the cache explicitly as an argument and return it along with the result, or use a state monad. The time complexity for the first calculation of `factorialMemoized n` is O(n) because each value from 0 to n is computed once. Subsequent calls for values already computed are O(1) due to cache lookup. Space complexity is O(n) to store the computed factorials up to `n` in the cache.

define Cache as a Map from key (Int) to value (Integer) define globalCacheFactorial as a mutable reference to a Cache, initialized as empty function factorialMemoized(n): if n is less than 0: throw error else if n is 0:...

This Haskell code generates the Fibonacci sequence as an infinite, lazy list. The `fibonacciSequence` definition is recursive and uses `zipWith (+) fibonacciSequence (tail fibonacciSequence)` to efficiently compute subse...

The `fibonacciSequence` is defined recursively. It starts with `0 : 1 : ...`. The rest of the sequence is generated by `zipWith (+) fibonacciSequence (tail fibonacciSequence)`. This means each subsequent element is the sum of the corresponding elements from the `fibonacciSequence` itself and its tail. For example, the third element is `fibonacciSequence[0] + fibonacciSequence[1]` (0 + 1 = 1), the fourth is `fibonacciSequence[1] + fibonacciSequence[2]` (1 + 1 = 2), and so on. This lazy evaluation means numbers are only computed when they are needed. The `takeFibonacci` function uses Haskell's built-in `take` function, which is also lazy. It handles the edge case where `n` is less than or equal to 0 by returning an empty list. The time complexity to generate the first `n` Fibonacci numbers is O(n) because each number is computed once. The space complexity is also O(n) to store the generated numbers up to `n`.

define fibonacciSequence as an infinite list: start with 0 then 1 then for each subsequent element, sum the previous two elements from the sequence itself define takeFibonacci(n): if n is less than or equal to 0: return...

This Haskell code demonstrates a thread-safe queue using Software Transactional Memory (STM). The `TQueue` is implemented using a `TVar` holding a list. `enqueue` and `dequeue` operations are performed within `STM` trans...

The `TQueue` is a wrapper around a `TVar [a]`, where `TVar` is a transactional variable. `newTQueue` creates a new `TVar` initialized with an empty list within an `STM` transaction. `enqueue` reads the current list from the `TVar`, appends the new element, and writes the updated list back. This is all done atomically within `STM`. `dequeue` reads the list; if it's empty, `retry` is called. `retry` aborts the current transaction and blocks the thread until one of the `TVar`s read in the transaction is modified, at which point the transaction is retried. If the list is not empty, it takes the head element, writes the tail back to the `TVar`, and returns the head. `isEmptyTQueue` simply checks if the list inside the `TVar` is empty. The `producer` and `consumer` functions demonstrate concurrent access to the queue. The `producer` adds random numbers, and `consumer`s remove them. The `atomically` function executes an `STM` action as a single, atomic transaction. Time complexity for `enqueue` and `dequeue` is O(1) on average for list operations (though append is O(N) for standard lists, a `Seq` would be better for true O(1)). Space complexity is O(N) where N is the number of elements in the queue.

define TQueue as a TVar holding a list of elements function newTQueue(): create a new TVar initialized with an empty list return TQueue containing the TVar function enqueue(queue, element): read the list from the queue's...

This Haskell code simulates an event sourcing system by defining an `AppState` and a list of `Event` types. The `applyEvent` function is a pure function that deterministically transforms the state based on a single event...

The `AppState` data type defines the current state of the system, which includes a counter and a list of messages. The `Event` data type enumerates all possible actions that can change the state. The `applyEvent` function is the core of the event sourcing logic; it takes the current `AppState` and an `Event`, and returns a new `AppState` reflecting the effect of that event. It's crucial that `applyEvent` is a pure function, meaning it always produces the same output for the same input and has no side effects. The `replayEvents` function uses `foldl'` (a strict left fold) to iterate through the list of `Event`s. It starts with `initialState` and applies each event sequentially using `applyEvent`. `foldl'` is used over `foldr` or a lazy `foldl` to ensure that the entire state is computed strictly, which is important for event sourcing to guarantee the correct final state. The time complexity of `replayEvents` is O(N * C), where N is the number of events and C is the complexity of `applyEvent`. If `applyEvent` is O(1) (like in this example for `IncrementCounter` and `AddMessage` if list append is amortized O(1) or using `Seq`), then `replayEvents` is O(N). Space complexity is O(N) for storing the event log and O(S) for the final state, where S is the size of the state.

define AppState with fields: counter (integer), messages (list of strings) define Event type with constructors: IncrementCounter(integer), AddMessage(string), ClearMessages, UnknownEvent(string) define initialState as Ap...

This Haskell code defines a safe division function using the Either monad to handle potential errors. It prevents division by zero by returning a Left value containing an error message. The `processDivisions` function ap...

The `safeDivide` function checks if the denominator is zero. If it is, it returns `Left "Error: Division by zero"`, indicating a failure. Otherwise, it performs the division and returns `Right (numerator / denominator)`, wrapping the successful result in the `Right` constructor. The `processDivisions` function recursively applies `safeDivide` to each pair in the input list, building a new list of `Either String Double` results. The `main` function demonstrates how to use these functions with sample data, including an explicit check for a negative divisor. The time complexity for `safeDivide` is O(1) as it's a single operation. The `processDivisions` function has a time complexity of O(n), where n is the number of division operations, due to the linear traversal of the input list. Space complexity for `processDivisions` is O(n) for storing the results.

function safeDivide(numerator, denominator): if denominator is 0: return Left("Error: Division by zero") else: return Right(numerator / denominator) function processDivisions(list_of_pairs): if list_of_pairs is empty: re...

This Haskell code implements Depth First Search (DFS) for an immutable graph represented by an adjacency map. The `dfs` function recursively explores nodes, keeping track of visited nodes using a `Set` to avoid cycles an...

The `dfs` function takes the graph, a starting node, and a set of already visited nodes. If the `startNode` is already in `visited`, it returns an empty list, terminating that path. Otherwise, it adds `startNode` to `visited`, retrieves its neighbors, filters out already visited neighbors, and then recursively calls `dfs` on each unvisited neighbor. The results from these recursive calls are concatenated, and the `startNode` is prepended to form the final list of visited nodes for this path. The `fullDfs` function iterates through all nodes in the graph. For each node, if it hasn't been visited yet, it initiates a `dfs` traversal from that node, effectively exploring a new connected component. The `visited` set is updated globally across component traversals. The time complexity for DFS 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. Space complexity is O(V) for the recursion stack and the `visited` set.

define Graph as a map from node ID to a list of adjacent node IDs function dfs(graph, startNode, visited_set): if startNode is in visited_set: return empty list else: add startNode to visited_set get neighbors of startNo...