Title: Functional Programming — LearnCoachAssist

Q: What is functional programming?
A: Functional programming is a declarative programming paradigm that treats computation as the evaluation of mathematical functions. It emphasizes immutability, pure functions, and avoiding side effects. Languages like Haskell, Erlang, Clojure, and F# are primarily functional.

Q: What is a pure function?
A: A pure function is a function that:
- Always returns the same output for the same input (deterministic)
- Has no side effects — it doesn't modify external state, perform I/O, or depend on mutable data
Example: const add = (a, b) => a + b; is pure, while Math.random() is not.

Q: What are side effects in functional programming?
A: Side effects are any observable changes a function makes beyond returning a value. Examples include:
- Modifying a global or external variable
- Writing to a file or database
- Printing to the console
- Making network requests
- Mutating input arguments
FP aims to isolate side effects from core logic.

Q: What is immutability?
A: Immutability means that once a data structure is created, it cannot be changed. Instead of modifying data, you create new copies with the desired changes. Benefits include:
- Easier reasoning about code
- Thread safety without locks
- Simpler debugging and testing
Example: const newArr = [...arr, newItem]; instead of arr.push(newItem);

Q: What are persistent data structures?
A: Persistent data structures always preserve previous versions of themselves when modified. They use structural sharing to efficiently reuse unchanged portions, avoiding full copies. Libraries like Immutable.js and languages like Clojure provide these. They enable O(log n) updates while maintaining immutability.

Q: What are first-class functions?
A: In a language with first-class functions, functions are treated as values — they can be:
- Assigned to variables: const greet = function() {}
- Passed as arguments to other functions
- Returned from other functions
- Stored in data structures
This is a prerequisite for functional programming.

Q: What are higher-order functions?
A: A higher-order function is a function that either:
- Takes one or more functions as arguments, or
- Returns a function as its result
Examples: map, filter, reduce, sort with a comparator. Example: const double = arr.map(x => x * 2);

Q: What is a closure?
A: A closure is a function that captures and remembers variables from its enclosing lexical scope, even after that scope has finished executing. Example:
function makeCounter() {
let count = 0;
return () => ++count;
}
The returned function closes over the count variable.

Q: What is lexical scoping?
A: Lexical scoping (static scoping) means a variable's scope is determined by its position in the source code, not by the runtime call stack. Inner functions can access variables from their enclosing functions. This is the foundation of closures and is used in most modern languages including JavaScript, Python, and Haskell.

Q: What is currying?
A: A currying transforms a function that takes multiple arguments into a sequence of functions, each taking a single argument. Example:
const add = a => b => a + b;
add(2)(3); // 5
Named after mathematician Haskell Curry. In Haskell, all functions are automatically curried.

Q: What is partial application?
A: Partial application fixes some arguments of a function, producing a new function with fewer parameters. Unlike currying, it can fix multiple arguments at once. Example:
const multiply = (a, b) => a * b;
const double = multiply.bind(null, 2);
double(5); // 10

Q: How does currying differ from partial application?
A: - Currying transforms a function of N arguments into N nested functions of 1 argument each — it's a structural transformation
- Partial application fixes some arguments and returns a function expecting the remaining arguments — it's about pre-filling values
Currying enables partial application but they are distinct concepts.

Q: How does map work in functional programming?
A: map applies a transformation function to each element of a collection, returning a new collection of the same size with transformed elements. The original collection is unchanged.
Example: [1, 2, 3].map(x => x * 2) returns [2, 4, 6].
Map preserves structure — it's a functor operation.

Q: How does filter work in functional programming?
A: filter takes a predicate function (returns true/false) and returns a new collection containing only elements for which the predicate returns true.
Example: [1, 2, 3, 4].filter(x => x % 2 === 0) returns [2, 4].
The original collection is not modified.

Q: How does reduce work in functional programming?
A: reduce (also called fold) combines all elements of a collection into a single value using an accumulator function and an initial value.
Example: [1, 2, 3].reduce((acc, x) => acc + x, 0) returns 6.
It's the most powerful of map/filter/reduce — both map and filter can be implemented using reduce.

Q: What is a monad?
A: A monad is a design pattern for composing functions that return wrapped values. It consists of:
- A type constructor (wraps a value)
- return / unit — wraps a value into the monad
- bind / flatMap — chains operations on wrapped values
Monads must satisfy three laws: left identity, right identity, and associativity.

Q: What is the Maybe monad?
A: The Maybe monad (called Optional in Java/Swift) handles values that might be absent. It has two states:
- Just(value) / Some(value) — contains a value
- Nothing / None — represents absence
It eliminates null checks by chaining operations that automatically short-circuit on Nothing.

Q: What is the Either monad?
A: The Either monad represents a value that can be one of two types:
- Right(value) — typically represents success
- Left(error) — typically represents failure
It provides a functional alternative to exceptions for error handling, allowing errors to be composed and chained cleanly.

Q: What is a functor?
A: A functor is a type that implements a map function, allowing you to apply a function to its wrapped value without unwrapping it. Functor laws:
- Identity: map(id) === id
- Composition: map(f . g) === map(f) . map(g)
Arrays, Maybe, and Either are all functors. Every monad is a functor, but not vice versa.

Q: What is an applicative functor?
A: An applicative functor extends functors by allowing you to apply a wrapped function to a wrapped value. It provides:
- pure — wraps a value
- ap / <*> — applies a wrapped function to a wrapped value
Applicatives sit between functors and monads in power: Functor < Applicative < Monad.

Q: What is pattern matching?
A: Pattern matching is a mechanism for checking a value against patterns and destructuring data. It's more powerful than switch/case:
match value {
Some(x) if x > 0 => "positive",
Some(_) => "non-positive",
None => "empty"
}
Used heavily in Haskell, Rust, Scala, and Elixir.

Q: What is recursion in functional programming?
A: Recursion is when a function calls itself to solve a problem by breaking it into smaller subproblems. In FP, recursion replaces loops since loops require mutable state. Example:
const factorial = n => n <= 1 ? 1 : n * factorial(n - 1);
Every recursive function needs a base case to prevent infinite recursion.

Q: What is tail call optimization (TCO)?
A: Tail call optimization is a compiler optimization where a function call in tail position (the last operation) reuses the current stack frame instead of creating a new one. This prevents stack overflow for deep recursion.
Tail-recursive factorial:
fact(n, acc=1) = n <= 1 ? acc : fact(n-1, n*acc)
Supported in Haskell, Scheme, and Erlang.

Q: What is referential transparency?
A: Referential transparency means an expression can be replaced by its value without changing the program's behavior. A function is referentially transparent if it always returns the same result for the same arguments and has no side effects.
Example: add(2, 3) can always be replaced with 5. This enables equational reasoning and compiler optimizations.

Q: What is function composition?
A: Function composition combines two or more functions to create a new function where the output of one becomes the input of the next. Notation: (f ∘ g)(x) = f(g(x))
Example:
const compose = (f, g) => x => f(g(x));
const addOneThenDouble = compose(double, addOne);
It reads right to left. Piping is left-to-right composition.

Q: What is piping in functional programming?
A: Piping is left-to-right function composition, which many find more readable. Data flows through a series of transformations:
pipe(addOne, double, toString)(5) applies addOne first, then double, then toString.
Languages like Elixir (|>), F# (|>), and Haskell (&) have native pipe operators.

Q: What is lazy evaluation?
A: Lazy evaluation delays the computation of an expression until its value is actually needed. Benefits:
- Avoids unnecessary computation
- Enables infinite data structures like infinite lists
- Improves performance for unused branches
Haskell is lazy by default. JavaScript generators and Python's range() use lazy evaluation.

Q: What is eager (strict) evaluation?
A: Eager evaluation evaluates expressions as soon as they are bound to a variable, regardless of whether the value is needed. Most languages (JavaScript, Python, Java) use eager evaluation by default. It's more predictable but may compute values that are never used, wasting resources.

Q: What are algebraic data types?
A: Algebraic data types (ADTs) are composite types formed by combining other types. Two main kinds:
- Sum types (tagged unions): a value is one of several variants — Either<A, B>, enum
- Product types: a value contains all fields — struct, tuple, record
Used extensively in Haskell, Rust, Scala, and ML family languages.

Q: What are sum types?
A: Sum types (also called tagged unions or discriminated unions) represent a value that is one of several possible variants. Example in Rust:
enum Shape { Circle(f64), Rectangle(f64, f64) }
The total number of possible values is the sum of each variant's possibilities. Combined with pattern matching, they enable exhaustive handling of all cases.

Q: What are product types?
A: Product types combine multiple values into one — tuples, structs, and records are product types. Example: (String, Int) is a product type where the total possible values are String values × Int values.
In Haskell: data Point = Point Double Double
Product types correspond to logical AND, while sum types correspond to logical OR.

Q: What is lambda calculus?
A: Lambda calculus is a formal system invented by Alonzo Church in the 1930s that forms the theoretical foundation of functional programming. It has only three constructs:
- Variables: x
- Abstraction (function definition): λx.body
- Application (function call): f x
It is Turing complete — any computation can be expressed in it.

Q: What is type inference?
A: Type inference is the compiler's ability to automatically deduce the types of expressions without explicit type annotations. Example in Haskell: add x y = x + y is inferred as Num a => a -> a -> a.
Algorithms like Hindley-Milner provide complete type inference. Languages like Haskell, ML, Rust, and TypeScript use type inference.

Q: What is declarative vs imperative programming?
A: - Imperative: describes how to do something step by step — loops, variable mutations, explicit control flow
- Declarative: describes what the result should be — SQL, HTML, FP expressions
FP is declarative: list.filter(x => x > 0).map(x => x * 2) says what to compute, not how to iterate.

Q: What is memoization?
A: Memoization is an optimization technique that caches the results of expensive function calls and returns the cached result for the same inputs. It works best with pure functions (guaranteed same output for same input).
Example: const memo = fn => { const cache = {}; return (...args) => cache[args] ??= fn(...args); };

Q: What is a fold operation?
A: Fold (also called reduce or accumulate) processes a data structure to build a return value. Two variants:
- foldl (left fold): processes left to right — [1,2,3] → ((0+1)+2)+3
- foldr (right fold): processes right to left — [1,2,3] → 1+(2+(3+0))
Left fold is tail-recursive; right fold works with infinite lists in lazy languages.

Q: What is an unfold operation?
A: Unfold (also called anamorphism) is the dual of fold — it builds a data structure from a seed value. While fold collapses a structure, unfold generates one.
Example: generating a list from 1 to n:
unfold(1, x => x > n ? null : [x, x+1])
produces [1, 2, 3, ..., n]. It's useful for generating sequences and streams.

Q: What is the difference between map and flatMap?
A: - map applies a function to each element, preserving structure: [[1],[2]].map(f) → [[f(1)],[f(2)]]
- flatMap (also called bind or >>=) applies a function and then flattens one level: [1,2].flatMap(x => [x, x*2]) → [1,2,2,4]
flatMap is the key monadic operation that enables chaining computations that return wrapped values.

Q: What are monoid laws and why do they matter?
A: A monoid is a type with:
- An associative binary operation: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
- An identity element: a ⊕ e = e ⊕ a = a
Examples: numbers with + and 0, strings with ++ and "", arrays with concat and []. Monoids enable safe parallel aggregation and fold operations.

Q: What is a thunk in functional programming?
A: A thunk is a zero-argument function used to delay evaluation of an expression. Instead of computing a value immediately, you wrap it in a thunk:
const thunk = () => expensiveComputation();
The value is only computed when the thunk is called. Thunks are the mechanism behind lazy evaluation in strict languages and are used in Redux middleware.

Q: What is point-free style?
A: Point-free style (tacit programming) defines functions without explicitly mentioning their arguments. Instead, you compose functions:
Pointed: const upper = s => s.toUpperCase();
Point-free: const getNames = map(prop('name'));
Benefits: cleaner code, emphasizes transformation pipeline. Overuse can reduce readability. Common in Haskell and Ramda.

Q: What is the IO monad?
A: The IO monad encapsulates side effects (file I/O, console output, network calls) in a pure functional context. In Haskell, all side effects must be wrapped in the IO monad:
main :: IO ()
main = putStrLn "Hello"
This keeps the type system honest — you can tell from a function's type whether it performs side effects.

Q: How does Haskell handle side effects?
A: Haskell uses the IO monad to handle side effects while maintaining purity. Side-effectful operations return IO a types. The do notation provides imperative-looking syntax:
do { name <- getLine; putStrLn ("Hello " ++ name) }
Pure code is strictly separated from effectful code at the type level, enforced by the compiler.

Q: What is referential transparency's benefit for testing?
A: Referential transparency makes testing dramatically simpler because:
- Functions are deterministic — same input always gives same output
- No need to set up or tear down external state
- No mocking of dependencies for pure functions
- Tests are independent and can run in parallel
You just assert that f(input) === expectedOutput.

Q: What are lenses in functional programming?
A: Lenses are composable getters and setters for working with immutable nested data structures. A lens focuses on a specific part of a data structure:
const nameLens = lens(prop('name'), assoc('name'));
view(nameLens, user) gets the name
set(nameLens, 'Alice', user) returns a new object with updated name. Libraries: Ramda, monocle-ts.

Q: What is eta reduction?
A: Eta reduction simplifies a function by removing redundant parameters when a function just passes its argument directly to another function:
Before: const double = x => multiply(2, x);
After: const double = multiply(2); (if multiply is curried)
This is a step toward point-free style. The term comes from lambda calculus: λx.f x reduces to f.

Q: What is a catamorphism?
A: A catamorphism is a generalization of fold — it deconstructs (tears down) a data structure according to its type's shape. For lists, it's foldr. For trees, it recursively processes each node. The term comes from Greek "kata" (downward). Catamorphisms are fundamental in recursion schemes, a framework for expressing recursive algorithms.

Q: What is trampolining?
A: Trampolining is a technique to achieve tail call optimization in languages that don't natively support it (like JavaScript). Instead of making recursive calls, the function returns a thunk. A trampoline loop then repeatedly calls thunks until a final value is reached:
while (typeof result === 'function') { result = result(); }
This prevents stack overflow for deep recursion.

Q: What are free monads?
A: Free monads separate the description of a computation from its interpretation. You define an algebra of operations as a functor, and the free monad gives you a monad for free. Benefits:
- Multiple interpreters (test vs production)
- Pure program descriptions
- Easy mocking and testing
Used in Haskell, Scala, and PureScript for effects systems.

Q: What is the difference between strict and non-strict evaluation?
A: - Strict (eager): arguments are fully evaluated before being passed to a function — used by most languages (JavaScript, Python, Java)
- Non-strict (lazy): arguments are evaluated only when needed — used by Haskell
Non-strict enables infinite data structures and can skip unnecessary computation, but makes reasoning about performance harder.

Q: What are the three monad laws?
A: The three laws every monad must satisfy:
- Left identity: return a >>= f ≡ f a
- Right identity: m >>= return ≡ m
- Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
Breaking a law means the monad will behave inconsistently across refactorings.

Q: What is the Functor identity law?
A: For any functor F, mapping the identity function over it must yield the same structure: F.map(x => x, fa) ≡ fa. If map(id) changes anything, the type is not a lawful functor.

Q: What is the Functor composition law?
A: Mapping a composition of two functions must equal composing two maps: fa.map(f).map(g) ≡ fa.map(x => g(f(x))). This guarantees that map preserves structure and doesn't reorder or drop elements.

Q: What is the Applicative identity law?
A: Applying the wrapped identity function to a wrapped value yields the wrapped value: pure(id) <*> v ≡ v. This is the applicative analogue of the functor identity law and ensures that wrapping the identity does nothing.

Q: What is the Applicative composition law?
A: pure((.) ) <*> u <*> v <*> w ≡ u <*> (v <*> w). The composition law guarantees that applicative effects combine the same way whether you nest them or use the ap operator chain.

Q: What is the Applicative homomorphism law?
A: Applying a pure-wrapped function to a pure value equals the pure result: pure f <*> pure x ≡ pure (f x). It ensures the applicative respects normal function application when no effects are involved.

Q: What is the Applicative interchange law?
A: u <*> pure y ≡ pure ($ y) <*> u. Interchange guarantees that a wrapped value on the right can be substituted with the equivalent applicative on the left, preserving semantics.

Q: What does Maybe.map return for Nothing?
A: Maybe.map(f, Nothing) short-circuits and returns Nothing — the function f is never applied. This is the core safety property: there is no way to crash on a missing value when chaining transformations.

Q: What does Either.map return for Left?
A: Either.map(f, Left(e)) returns Left(e) unchanged. Only the Right branch is transformed. Combined with flatMap, errors propagate through the entire chain without explicit checks.

Q: What is bind (>>=) in Haskell?
A: bind chains a monadic computation: m >>= k takes a monadic value m :: M a and a function k :: a -> M b, returning M b. It is the fundamental sequencing operation — return alone only wraps, while bind actually threads values through.

Q: What is the State monad?
A: The State monad models computations that thread mutable state through pure functions. A State s a represents a function s -> (a, s). The state is never actually mutated — each step returns a new state alongside its value, preserving referential transparency.

Q: What is the Reader monad?
A: The Reader monad models computations that read from a shared environment. Reader r a is r -> a. It is useful for dependency injection in pure code: pass config once, read it inside any nested function without explicit threading.

Q: What is the Writer monad?
A: The Writer monad accumulates a log or telemetry alongside a computed value. Writer w a carries (a, w), where w is a monoid (so logs can be combined associatively). Common uses: logging, profiling, collecting errors.

Q: What is the List monad?
A: The List monad represents non-deterministic computation: a list is a set of possible results. [1,2] >>= \x -> [x, -x] produces [1,-1,2,-2]. It is the basis of list comprehensions in Haskell and underlies generator-style enumeration in other languages.

Q: What is the Continuation monad?
A: The Continuation monad (Cont r a) represents a computation in terms of a callback representing the rest of the computation. It is the functional encoding of goto / early return and powers advanced control structures like coroutines and async/await.

Q: What is a type class (Haskell)?
A: A type class is Haskell's mechanism for ad-hoc polymorphism — defining behavior that works across many types. Example: class Eq a where (==) :: a -> a -> Bool. Instances provide implementations per type. Type classes are not classes in the OO sense; they are interfaces with no inheritance.

Q: What is the Eq type class?
A: Eq provides (==) and (/=) for equality comparison. Any type with a meaningful notion of equality can be an Eq instance. Eq is a superclass of Ord, so any ordered type must also be equatable.

Q: What is the Ord type class?
A: Ord provides (<), (<=), (>), (>=), compare, and uses min/max. It requires Eq as a superclass. Ordering must be total: compare a b yields LT, EQ, or GT exactly.

Q: What is the Functor type class?
A: Haskell's class Functor f where fmap :: (a -> b) -> f a -> f b. Note f is a type constructor taking one argument — Maybe, [], Either e are functors. f cannot be a plain type like Int because it has kind * -> *.

Q: What is the Monad type class?
A: Haskell: class Monad m where return :: a -> m a; (>>=) :: m a -> (a -> m b) -> m b. Every monad must satisfy the three monad laws. Note that Applicative is a superclass of Monad in modern Haskell.

Q: What is the Show type class?
A: Show provides a conversion to a human-readable String via show. It is mostly used for debugging and deriving Show generates a default implementation that prints the constructor and fields.

Q: What is the Semigroup type class?
A: class Semigroup a where (<>) :: a -> a -> a — a type with an associative binary operation. Every monoid is a semigroup, but a semigroup has no required identity. NonEmpty, Max, and function composition are semigroups without identity elements.

Q: What is the Monoid type class?
A: class Monoid a where mempty :: a; (<>) :: a -> a -> a. It extends Semigroup with mempty, the identity: mempty <> x ≡ x <> mempty ≡ x. String with concatenation, [a] with ++, and numbers with addition are monoids.

Q: What is a function monoid?
A: Functions form a monoid under composition: mempty = id and (<>) = (.). This means mconcat over a list of functions composes them all, enabling foldMap (.) id style aggregation. Function monoids are central to Endomorphism-based optimization.

Q: What is an Endomorphism?
A: An Endomorphism is a function from a type to itself: type Endo a = a -> a. With composition, all Endo a form a monoid. They enable efficient repeated transformation, e.g. foldMap Endo [f,g,h] gives a single composed function.

Q: What is a natural transformation?
A: A natural transformation is a mapping between two functors that preserves structure: a function forall a. F a -> G a that commutes with fmap. Example: head :: [a] -> Maybe a is natural. Natural transformations are the morphisms of the category of functors.

Q: What is a type variable?
A: A type variable is a placeholder in a type signature, written in lowercase: a, b, f. id :: a -> a means "for any type a, here is a function from a to a." They enable parametric polymorphism.

Q: What is parametric polymorphism?
A: Parametric polymorphism means a function works uniformly across all types, with no case analysis on type. id :: a -> a cannot inspect a — it must work for any. Compare with ad-hoc polymorphism (type classes) and subtype polymorphism (OO inheritance).

Q: What is ad-hoc polymorphism?
A: Ad-hoc polymorphism is when a function name has different implementations for different types. Haskell's type classes are the canonical example: (+) works for Int, Double, Complex, each with its own instance. Often called overloading.

Q: What is the Hindley-Milner algorithm?
A: Hindley-Milner (HM) is the classical type-inference algorithm that can deduce the most general type of an expression without annotations. It uses unification of type equations. It underpins Haskell, ML, and OCaml. Limitations: it cannot infer higher-rank types.

Q: What is a higher-kinded type?
A: A higher-kinded type is a type constructor that takes another type constructor as an argument. MaybeT has kind (* -> *) -> * -> *. Haskell supports them; many other languages (including Rust, Java) do not, which is why their Monad emulation is limited.

Q: What is kind in Haskell?
A: A kind is the "type of a type." Int has kind *. Maybe has kind * -> *. Functor has kind ((* -> *) -> *) -> Constraint. The kind system prevents nonsense like Maybe Int Int.

Q: What is the MaybeT monad transformer?
A: MaybeT m a is a monad transformer that adds Maybe short-circuiting to an underlying monad m. do { x <- ma; y <- mb; return (x + y) } yields Nothing if either step yields Nothing, even if ma performs effects.

Q: What is the EitherT monad transformer?
A: EitherT e m a lifts Either e over monad m, allowing error handling inside effectful code. Common in production Haskell: ExceptT String IO User chains IO with explicit error propagation through throwError and catchError.

Q: What is the ReaderT pattern?
A: ReaderT r m a combines a read-only environment with any monad m. It is the basis of mtl-style effects in Haskell: AppM = ReaderT Config IO, providing both config access and IO via the same stack.

Q: What is a type signature in Haskell?
A: A type signature declares the type of a binding: add :: Num a => a -> a -> a. The Num a => is a type class constraint requiring a to be numeric. Signatures serve as documentation and catch bugs at compile time.

Q: What does the expression (flip (.) map) do?
A: flip (.) map produces map . f, i.e. post-composition. The trick: flip swaps the argument order of composition, so it becomes "function, then function" — useful for building pipes and lenses in point-free style.

Q: What is the applicative-do syntax?
A: Haskell's ApplicativeDo extension lets you desugar do-notation using <*> instead of >>= when the bound names are not reused. This enables do { x <- mx; y <- my; return (x,y) } to run effects concurrently, not sequentially.

Q: What is anamorphism?
A: An anamorphism is the dual of catamorphism: it builds a structure from a seed by unfolding. unfoldr :: (b -> Maybe (a, b)) -> b -> [a] is the list anamorphism. Anamorphisms generate, catamorphisms consume.

Q: What is a hylomorphism?
A: A hylomorphism is a fusion of an anamorphism (unfold) followed by a catamorphism (fold) without building the intermediate structure. Used to express divide-and-conquer algorithms (like merge sort) with constant memory in a streaming/recursion-schemes sense.

Q: What is a Church encoding?
A: A Church encoding represents data as higher-order functions. Church Bool = forall a. a -> a -> a; True = \t _ -> t. Church numerals: n = \f x -> iterate f x applied n times. It's a way to express all of computation using only lambdas.

Q: What is a Scott encoding?
A: The Scott encoding represents data as functions that case-analyze themselves: ScottList a = forall r. (a -> ScottList a -> r) -> r -> r. Like Church encoding it is lambda-only, but it supports strict pattern matching, making it suitable for strict languages.

Q: What is a fixed-point combinator?
A: The Y combinator enables anonymous recursion in lambda calculus: Y f = f (Y f). It computes the least fixed point of f, i.e. x = f x. Foundational for defining recursive functions without named bindings, and central to denotational semantics.

Q: What is the difference between Y and Z combinators?
A: - Y: Y f = (\x -> f (x x)) (\x -> f (x x)) — works in lazy languages like Haskell
- Z: Z f = (\x -> f (\y -> x x y)) (\x -> f (\y -> x x y)) — works in strict languages because it wraps the recursive call in a thunk

Q: What is a combinator?
A: A combinator is a function whose only free variables are its arguments — it does not reference external state. const x _ = x, flip f a b = f b a, and the Y combinator are all combinators. Combinator-heavy code is highly portable and easy to test.

Q: What is the K combinator?
A: K x _ = x — the K combinator takes two arguments and returns the first. In point-free style, K x is a constant function that ignores its argument. Useful for "ignore the second value" patterns.

Q: What is the S combinator?
A: S x y z = x z (y z) — the S combinator is generalized application. Combined with K, the pair {S, K} forms a Turing-complete basis for computation, known as SKI calculus.

Q: What is SKI calculus?
A: SKI calculus is a minimal combinator calculus with three primitives: S, K, and I (identity). It is computationally equivalent to lambda calculus but has no variables or lambdas. Useful for studying evaluation strategies without alpha-conversion.

Q: What is beta reduction?
A: Beta reduction is the evaluation rule for function application: (λx. body) arg ⇒ body[x := arg]. It is the computational heart of lambda calculus. Normal order reduction always reduces the leftmost-outermost redex; applicative order reduces inside-out.

Q: What is alpha equivalence?
A: Alpha equivalence states that λx. x and λy. y are the same function — bound variable names don't matter. In languages that expose it, refactoring a parameter name must not change behavior. Alpha-conversion renames bound variables consistently.

Q: What is eta expansion?
A: Eta expansion is the inverse of eta reduction: it wraps a function with a lambda to make its behavior explicit. map reverse might be eta-expanded to \xs -> map reverse xs when you need to make a type signature check or delay evaluation.

Q: What is Church-Rosser theorem?
A: The Church-Rosser theorem says lambda calculus has the confluence property: any two reduction sequences from the same term can be extended to meet at a common result. This guarantees that a term's normal form is unique (if it exists), enabling deterministic evaluation strategies.

Q: What is a weak head normal form (WHNF)?
A: A term is in WHNF when its outermost structure is not a redex: either a constructor, lambda, or partial application. In Haskell, let x = 1 + 2 : l leaves x in WHNF even though the addition isn't done. Full evaluation to NF is sometimes called "NF" or "spine normal form."

Q: What is a thunk leak?
A: A thunk leak occurs when a lazy language keeps unevaluated thunks in memory because the surrounding structure is referenced. The classic case: let xs = [1..] in sum (take 5 xs) in naive evaluation retains the whole infinite list. Space-leak profiling tools (in GHC) can pinpoint them.

Q: How does Haskell implement lazy evaluation?
A: Haskell compiles expressions to graph reductions of thunks. A thunk holds an unevaluated expression plus its environment. When forced, the thunk is replaced by its value (a heap update). Sharing is captured by pointer identity, not copying.

Q: What is a stream in functional programming?
A: A stream is a lazy, possibly infinite sequence. streamFrom n = n : streamFrom (n+1) is an infinite stream. Streams enable processing of unbounded data with bounded memory via take, map, and filter. They are the backbone of Rx-style reactive programming.

Q: What is a generator in JavaScript?
A: A generator is a function that can pause and resume, yielding values lazily: function* g() { yield 1; yield 2; }. Generators model streams and coroutines. They are not strict FP, but combine well with map/filter for lazy pipelines.

Q: What is the difference between iterators and streams?
A: - Iterator: pulls values on demand; state is usually external; termination is signaled by done or exception
- Stream: pushes values through a pipeline; state is internal; may be infinite
Streams are more composable; iterators are simpler. Functional reactive programming uses streams.

Q: What are transducers?
A: Transducers are composable algorithmic transformations decoupled from the input/output context. A map transducer can be reused across lists, streams, channels, and async iterables: const xform = map(x => x*2). They avoid intermediate collections, unlike the list-comp-style map.

Q: What is the difference between mapcat and flatMap?
A: They are the same operation under different names: mapcat f = concat . map f in Haskell, flatMap in JavaScript, bind in monadic contexts. All flatten one level after mapping with a function that returns multiple values.

Q: What is the Compose functor?
A: Compose f g a nests two functors: f (g a). It is itself a functor: map f (Compose fga) = Compose (fmap (fmap f) fga). Useful for mapping over structures like Maybe [a] or IO (Either e a) as a single layered structure.

Q: What is the Identity functor?
A: Identity a is a no-op wrapper: Identity x = Identity x; runIdentity (Identity x) = x. It is the identity functor on the functor category. Useful in monad transformer stacks as a base layer, and in mapAccumL optimizations.

Q: What is a comonad?
A: A comonad is the categorical dual of a monad: it provides extract :: w a -> a and duplicate :: w a -> w (w a). Examples: the zipper data structure is a comonad, as is the environment reader. Comonads model context-dependent computation.

Q: What is a zipper?
A: A zipper is a data structure that pairs a focused element with its surrounding context, enabling O(1) navigation and updates in an otherwise immutable structure. List zippers: Zipper a = Zip [a] a [a]. The zipper is a comonad; extract returns the focus.

Q: What is a cofree comonad?
A: The cofree comonad of a functor F is Cofree f a = (a, f (Cofree f a)): a value with a branching tree of future values. It is dual to the free monad. Used in FRP to model "values with a stream of future derivatives."

Q: What is a comonad law?
A: Comonads must satisfy:
- Left identity: extract . duplicate = id
- Right identity: fmap extract . duplicate = id
Together with the associativity condition, these ensure the contextual structure behaves correctly.

Q: What is a profunctor?
A: A profunctor is a type constructor p of kind * -> * -> * that is contravariant in its first argument and covariant in the second. Example: (->) r b — functions from r to b. Profunctors model bimappable structures, foundational to optics.

Q: What is an optic?
A: An optic is a composable abstraction for accessing parts of a data structure. The optic family includes lenses (focus on a substructure), prisms (focus on a constructor), traversals (zero-or-more), and isos (bijections). Optics compose: lens1 . lens2 focuses deeper.

Q: What is a prism?
A: A prism is an optic that focuses on a single constructor of a sum type. _Left :: Prism (Either a b) (Either a' b) a a' — you can preview, review, or set values inside the Left branch. Combined with Iso and Lens, prisms form a uniform view of ADTs.

Q: What is a traversal?
A: A traversal is an optic that focuses on zero or more elements at once, like every element of a list. traverse :: Applicative f => (a -> f b) -> s -> f (t b). Traversals are the most general optic: lenses and prisms are special cases.

Q: What is an iso?
A: An iso (isomorphism) is a lossless optic: a bijection between two types. iso :: (s -> a) -> (a -> s) -> Iso s s a a. Isos are used for type conversions (e.g. iso Map.toList Map.fromList) and protocol/serialization boundaries.

Q: What is a getter?
A: A getter is a read-only optic: view :: Getter s a -> s -> a. It composes with other getters but cannot modify. Useful for deriving summary fields: views (traversed . _2) maximum returns the max of all seconds in a list of pairs.

Q: What is a setter?
A: A setter is a write-only optic: over :: Setter s a -> (a -> a) -> s -> s. Setters cannot read individual values. They are most useful in bulk updates: over traversed (+1) [1,2,3] = [2,3,4].

Q: What is a fold in the optics sense?
A: An optical fold is a read-only traversal: foldOf :: Fold s a -> s -> [a] (or to any Monoid). The folded traversal of a list gives its elements; has checks non-emptiness; sumOf sums. Folds are the only optic that reduces to a value.

Q: What is the difference between a lens and a setter?
A: - Lens: read AND write a subfield — view, set, over
- Setter: only write (or transform) — no way to extract the current value
Lenses have full focus; setters exist when you can map a function over zero-or-more elements.

Q: How does OCaml differ from Haskell?
A: - OCaml is strict by default (Haskell is lazy)
- OCaml has mutable fields and ref cells built in
- OCaml's type system is more permissive (e.g. object, mutable); Haskell forbids impurity in pure code
- OCaml uses modules (signatures + structures) as a primary abstraction; Haskell uses type classes
- Both have algebraic data types and pattern matching

Q: What are F# computation expressions?
A: Computation expressions (CEs) are F#'s syntax for defining custom computation syntax using let!, do!, and yield. They generalize monads, async, sequences, and queries. async { let! x = fetchUrl() ; ... } is a CE in action.

Q: What is F#'s unit type?
A: unit in F# (and OCaml) is a type with exactly one value, written (). It is the type of statements that compute "nothing of interest." Haskell's analogue is () with value (); in C-like languages the closest is void as a return type.

Q: What is the async monad in F#?
A: F#'s Async is a computation expression for asynchronous, parallel, and background work: async { let! r = http.Get(url) ; return r.Body }. It is conceptually similar to a monad but does not require language-level monad support — CE syntax is enough.

Q: What is the difference between Elixir's |> and Haskell's . ?
A: - |> (Elixir, F#): left-to-right data flow. x |> f(y) is f(x, y)
- . (Haskell): right-to-left function composition. f . g is \x -> f (g x)
Pipes are data-focused; composition builds functions. F# has both: |> and >>.

Q: How does Clojure handle immutability?
A: Clojure's persistent data structures (lists, vectors, maps, sets) are immutable with structural sharing. "Updates" return new collections that share most of their internals with the old. Trie-based vectors give ~O(log32 n) updates with structural sharing for cheap copies.

Q: What are transducers in Clojure?
A: Clojure transducers (map, filter, cat as transducer forms) are composable algorithmic transformations decoupled from the data source. (into [] (map inc) (filter odd? [1 2 3 4])) composes map+filter and applies them during reduction, avoiding intermediate vectors.

Q: What is the difference between reduce and transduce in Clojure?
A: - reduce: applies a single transformation during fold
- transduce: composes multiple transformations then applies them during a single fold
transduce avoids intermediate collections when chaining many operations, dramatically improving performance.

Q: What is Erlang's process model?
A: Erlang models concurrency as lightweight isolated processes with message passing. Each process has its own heap, GC, and mailbox. There is no shared memory. spawn creates a process, ! sends a message, receive receives. Crash isolation is built in.

Q: What is the "let it crash" philosophy?
A: Originating in Erlang: rather than defensively handling every error, let processes fail and rely on supervisors to restart them. Defensive coding often hides bugs; crash + restart is observable, fast, and self-healing. This aligns with FP's preference for isolating side effects.

Q: What is immutability's effect on concurrency?
A: Immutable data is automatically thread-safe: no lock is needed because no thread can mutate shared state. This eliminates a whole class of bugs (data races, deadlocks). It is the central reason Erlang, Clojure, and Haskell scale to massive concurrency.

Q: What is a software transactional memory (STM)?
A: STM provides atomic, isolated access to shared mutable state without explicit locks. Transactions read and write to TVars in Haskell or refs in Clojure; on conflict, the runtime retries automatically. STM is composable: any function can run inside a transaction.

Q: What is structural sharing?
A: Structural sharing means new versions of a persistent data structure reuse unchanged subtrees from the old version. A modified [1,2,3,4,5] vector with the third element changed typically allocates only O(log n) new nodes, not a full O(n) copy. This is how Clojure and Immutable.js get O(log n) "copy" costs.

Q: What is a trie in persistent data structures?
A: Many persistent vectors (including Clojure's) are implemented as tries with branching factor 32. Updating element i requires copying only O(log32 n) nodes along the path — effectively O(1) for vectors up to billions of elements.

Q: What is the cons list?
A: A cons list is a singly linked list built from cons :: a -> [a] -> [a]. [1,2,3] is sugar for 1 : 2 : 3 : []. Prepending is O(1); random access is O(n). Persistent cons lists form the basis of Lisp/Scheme/Clojure and many FP idioms.

Q: What is the difference between foldl and foldr?
A: - foldl: traverses the list left-to-right, tail-recursive, but cannot stop early on infinite lists
- foldr: traverses right-to-left, builds a chain of thunks, can be lazy on infinite lists, but not tail-recursive
Use foldr when the structure is recursive (like building a list); use foldl' (strict) for accumulation.

Q: What is foldl' and why prefer it?
A: foldl' (Haskell) is the strict left fold: it forces accumulator updates before continuing, preventing the buildup of thunks that foldl accumulates. For numerical sums, foldl' (+) 0 runs in constant space; foldl (+) 0 builds a chain of unevaluated additions — a space leak.

Q: What is a difference list?
A: A difference list is a list represented as a function from a list to a list: type DList a = [a] -> [a]. Append becomes function composition: dl1 <> dl2 = dl1 . dl2, giving O(1) append. Useful in logic programming (Prolog) and Haskell's Show instance for performance.

Q: What is a rose tree?
A: A rose tree Tree a = Node a [Tree a] is a tree with arbitrarily many children per node. It's the canonical data structure for ASTs, plans, and proof trees. Combinators like drawTree render them; foldTree generalizes fold over them.

Q: What is a finger tree?
A: A finger tree is a general-purpose persistent sequence with amortized O(1) cons and snoc, O(log n) append, and O(log n) search. It can be parameterized to act as a sequence, priority queue, or ordered set. Used in Haskell's Data.Sequence.

Q: What is a function's signature arrow?
A: In Haskell, the arrow -> in a -> b -> c is right-associative: it parses as a -> (b -> c). A function of two arguments is a function that returns a function. This is the same insight as currying at the type level.

Q: What is a record syntax in Haskell?
A: data Person = Person { name :: String, age :: Int } defines a record with field accessors automatically. name p extracts the name; p { age = 30 } updates the age (returning a new record). Records improve readability over positional constructors.

Q: What is a newtype?
A: newtype UserId = UserId Int declares a zero-cost wrapper around an existing type. At runtime, UserId is identical to Int (no tag, no overhead), but the type system treats them as distinct. Newtypes are how Haskell adds semantic distinction without performance cost.

Q: What is the difference between data and newtype?
A: - data: introduces a new algebraic type with a constructor; can have multiple fields and lazy fields
- newtype: introduces a single-constructor wrapper; identical at runtime, but distinct at the type level
Use newtype for type-safe wrappers (e.g. newtype Celsius = Celsius Double).

Q: What is Generalized Algebraic Data Type (GADT)?
A: GADTs extend ADTs with type-equality constraints in constructors: data Expr a where IntE :: Int -> Expr Int; BoolE :: Bool -> Expr Bool. They enable type-indexed data and are the basis for typed ASTs, embedded DSLs, and type-safe resource management.

Q: What is a phantom type?
A: A phantom type is a type parameter that does not appear in the constructor: data Token a = Token String — the a is phantom. Phantom types encode extra type-level information (e.g. Token "user" vs Token "admin") without runtime cost.

Q: What is type families in Haskell?
A: Type families are type-level functions: type family Element c maps a container type to its element type. Element [a] = a. They enable type-level computation, replacing some uses of functional dependencies. Combined with type classes, they power advanced type-level programming.

Q: What is DataKinds extension?
A: DataKinds promotes ordinary data constructors to the kind level. data Nat = Zero | Succ Nat becomes a kind with inhabitants 'Zero, 'Succ 'Zero, etc. Combined with type-level naturals, you can express vector length in its type: Vec n a.

Q: What is a singleton type?
A: A singleton type has exactly one inhabitant per type-level tag: data SNat (n :: Nat) where SZero :: SNat 'Zero; SSucc :: SNat n -> SNat ('Succ n). They bridge the value level and the type level, allowing runtime reflection of compile-time information.

Q: What is dependently-typed programming?
A: In dependent types, types can depend on values: Vec n a has n as both a runtime parameter and a type-level index. Languages: Idris, Coq, Agda. They enable proofs-as-programs, refined types, and total verification, but type inference is hard.

Q: What is Idris?
A: Idris is a dependently-typed functional language with syntax like Haskell. It supports full dependent types, totality checking, and tactics-based theorem proving. It targets compilation to native code, JavaScript, and C, making it practical for systems where types carry significant information.

Q: What is the difference between a monad and an applicative?
A: - Applicative: wrapped function applied to wrapped values, but the choice of function cannot depend on previous values
- Monad: the function applied to wrapped values can depend on previous values
Maybe a is monadic because the next step can branch on whether the previous was Just or Nothing.

Q: What is the difference between join and bind?
A: - join :: Monad m => m (m a) -> m a flattens one level
- bind is join . fmap f in disguise
Given m >>= f = join (fmap f m), join is the simpler primitive from which bind is derived.

Q: What is a Free monad in Haskell?
A: data Free f a = Pure a | Free (f (Free f a)). The Free monad lifts any functor f into a monad, with no operations beyond the ones f provides. This separates description (the Free structure) from interpretation (a natural transformation f a -> m a).

Q: What is an interpreter in the Free monad sense?
A: An interpreter is a function interp :: Free f a -> m a that walks the free-monad tree, folding each layer with a natural transformation. The same Free program can have a real-world interpreter (IO) and a test interpreter (pure values), enabling effect testing without mocks.

Q: What is the Coyoneda lemma?
A: Coyoneda lemma: for any functor f, f a is isomorphic to Free (Coyoneda f) a. Coyoneda f a = Coyoneda (k -> a) (f k) — it represents the image of fmap explicitly. This makes any functor a Functor automatically, simplifying Free monad construction.

Q: What is the Yoneda lemma?
A: Yoneda lemma: forall b. (a -> b) -> f b is isomorphic to f a. Intuitively, a functor is determined by how it behaves under fmap — you don't need to know its internal structure, just its action on morphisms. The lemma is foundational to category theory and Haskell's optimization patterns.

Q: What is a Natural Number object?
A: In category theory, a natural number object (NNO) is an object with morphisms zero :: 1 -> N and succ :: N -> N satisfying the Peano axioms. In Haskell, lists [a] parameterized by a form a NNO, and Church numerals are another representation.

Q: What is the Writer monad's logging problem?
A: The Writer monad appends to a log on every bind, but does not explicitly thread the log value. For long-running computations, the log can grow unbounded in memory. Solutions: streaming writers (one log line at a time), effects-based logging (MTL style), or a custom monad transformer.

Q: What is MonadFail?
A: MonadFail m => Monad m where fail :: String -> m a. In GHC, pattern matches in do-notation use fail when they fail. Modern Haskell restricts MonadFail to Monads that are also MonadFail (e.g. Maybe, lists), excluding IO in pure code.

Q: What is a bifunctor?
A: A bifunctor is a type constructor of kind * -> * -> * that is a functor in both arguments: class Bifunctor f where bimap :: (a -> b) -> (c -> d) -> f a c -> f b d. Either and (,) (pairs) are bifunctors. Laws: bimap id id = id and composition preservation.

Q: What is a contravariant functor?
A: A contravariant functor applies a function to its input in the opposite direction: class Contravariant f where contramap :: (a -> b) -> f b -> f a. The Predicate a = a -> Bool type is contravariant: contramap length (\_ -> True) is a "lengthy" predicate.

Q: What is a contravariant applicative?
A: A contravariant applicative uses (<<) (also called contramap) instead of <*>. Its laws: pure id &<< v = v and pure (.) &<< u &<< v &<< w = u &<< (v &<< w). Predicates and comparisons are contravariant applicatives.

Q: What is foldMap and why is it useful?
A: foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m maps each element to a monoid and combines them. It is the most general fold — sum is foldMap Sum, length is foldMap (\_ -> Sum 1). foldr and foldl' can both be derived from it.

Q: What is the difference between Foldable and Functor?
A: - Functor: maps each element to a new value — preserves the structure
- Foldable: collapses the structure to a single value (or monoid)
A Tree can be a Functor (map over leaves) and a Foldable (sum the leaves). IO is Functor but not Foldable.