Haskell & Functional Programming Concepts Questions

Haskell language fundamentals and functional programming concepts, including pure functions, immutability, higher-order functions, recursion, lazy evaluation, the type system and type classes, and core FP abstractions such as Functor, Applicative, and Monad (including monadic IO), along with common patterns and idioms used in Haskell programming.

EasyTechnical

27 practiced

Define a simple binary tree ADT in Haskell:

haskell

data Tree a = Leaf | Node (Tree a) a (Tree a)

Implement an inorder traversal `inorder :: Tree a -> [a]` that returns the values in-order. Explain how ADTs make pattern matching and structural recursion straightforward in Haskell.

Sample Answer

We can implement inorder traversal directly by pattern matching on the Tree ADT and using structural recursion: traverse left subtree, visit node value, then traverse right subtree, concatenating lists.

haskell

data Tree a = Leaf | Node (Tree a) a (Tree a)

-- In-order traversal: left, root, right
inorder :: Tree a -> [a]
inorder Leaf = []
inorder (Node left x right) = inorder left ++ [x] ++ inorder right

Key points:- Pattern matching: The type definition exposes two constructors (Leaf, Node). Matching them in function clauses makes control flow explicit and concise.- Structural recursion: Recursion follows the shape of the data — to process a Node we recursively process its left and right subtrees and combine results.- Purity and safety: No null checks needed; Leaf is an explicit base case so functions are total for this ADT.- Complexity: Time O(n) where n = number of nodes (each node visited once). The list concatenation using ++ can make this O(n^2) in the worst construction pattern; for large trees consider difference lists or an accumulator-based traversal to get O(n) with prepending:

haskell

inorderAcc :: Tree a -> [a] -> [a]
inorderAcc Leaf acc = acc
inorderAcc (Node l x r) acc = inorderAcc l (x : inorderAcc r acc))

inorder2 t = inorderAcc t []

Edge cases: empty tree returns []; single-node tree returns single-element list.

MediumTechnical

26 practiced

Explain what a lens is and why it's useful for updating deeply nested immutable structures. Implement a minimal manual lens for a simple record type (no external library): create `get` and `set` functions for a nested field and show how to compose them.

Sample Answer

A lens is a first-class getter/setter pair that focuses on a subpart of a larger immutable structure. It abstracts "how to read" and "how to produce an updated copy" so you can compose small updates into modifications of deeply nested data without boilerplate copying. Lenses improve readability, reuse, and composability.

Approach: implement a minimal lens type as (s -> a, s -> a -> s) = (getter, setter), provide compose to focus deeper, and show usage.

haskell

-- Minimal lens: (getter, setter)
type Lens s a = (s -> a, s -> (a -> s))

-- Example records
data Address = Address { city :: String, zipCode :: Int } deriving Show
data Person  = Person  { name :: String, address :: Address } deriving Show

-- Primitive lenses
addressL :: Lens Person Address
addressL = (address, \p newAddr -> p { address = newAddr })

cityL :: Lens Address String
cityL = (city, \a newCity -> a { city = newCity })

-- Compose two lenses: focus through outer then inner
compose :: Lens s a -> Lens a b -> Lens s b
compose (get1, set1) (get2, set2) =
  ( \s -> get2 (get1 s)
  , \s newB -> set1 s (set2 (get1 s) newB)
  )

-- Derived lens for nested field
personCityL :: Lens Person String
personCityL = compose addressL cityL

-- Helpers
view :: Lens s a -> s -> a
view (g,_) = g

set :: Lens s a -> a -> s -> s
set (_,sF) = sF

-- Example
p0 = Person "Alice" (Address "OldTown" 12345)
p1 = set personCityL "NewCity" p0
-- view personCityL p1 == "NewCity"

Key points:- get returns the focused value; set produces a new outer structure with that part replaced.- compose chains lenses without writing manual nested updates.- Time/space: updates allocate new copies along the path (shallow copies for immutable fields), proportional to nesting depth.Edge cases: ensure setters preserve unchanged fields; for optional paths you'd extend lens to handle Maybe (partial lenses) or use traversal-like patterns.

MediumTechnical

28 practiced

Explain higher-kinded types (types that take type constructors as parameters) in Haskell. Use `Functor`'s kind `* -> *` as an example and show a small example of a typeclass that requires `* -> * -> *` kinds (e.g., `Bifunctor`).

Sample Answer

Higher-kinded types are types that take type constructors as parameters — i.e. their arguments are themselves types that have kinds. In Haskell kinds classify types, like types classify values. The basic kind is * (a concrete type). A Functor works over type constructors of kind * -> * (they take one concrete type to produce a concrete type), e.g. Maybe :: * -> *.

Functor's class:

haskell

class Functor f where
  fmap :: (a -> b) -> f a -> f b
-- f :: * -> *
-- fmap maps over the inner 'a'

Here f has kind * -> * (e.g. Maybe, [], Identity).

For type constructors that take two type parameters (kind * -> * -> *), use Bifunctor:

haskell

class Bifunctor p where
  bimap :: (a -> c) -> (b -> d) -> p a b -> p c d
-- p :: * -> * -> *

Example instance for Either:

haskell

instance Bifunctor Either where
  bimap f _ (Left a)  = Left (f a)
  bimap _ g (Right b) = Right (g b)

Key ideas:- Kinds: * (concrete), k1 -> k2 (type constructors).- Higher-kinded types let you abstract over containers, effects, or type constructors with varying arity.- You can write classes constrained to specific kinds (e.g., * -> *, * -> * -> *).

HardTechnical

27 practiced

Implement a bounded worker pool in Haskell that processes tasks concurrently: use `async` or `forkIO` plus a bounded `TChan`/`TBQueue` for job queueing, spawn N workers, support graceful shutdown, and allow cancellation of in-flight tasks. Provide code sketches and discuss how you'll handle exceptions and resource cleanup.

Sample Answer

Approach summary:- Use TBQueue as a bounded job queue.- Spawn N worker threads (Async) that repeatedly dequeue jobs and run them with Async so each job can be cancelled independently.- Track in-flight job Asyncs in a TVar (Set/Map) for cancellation.- Support graceful shutdown: stop accepting new jobs, wait for queue to drain and for in-flight jobs to finish.- Support immediate cancellation: cancel all in-flight jobs and worker threads.- Handle exceptions: catch job exceptions (so a crash in a job doesn't kill the worker), log/propagate via result channels, and ensure resources (workers and Asyncs) are cancelled on shutdown.

Code sketch (concise, illustrative):

haskell

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Concurrent.Async
import Control.Concurrent.STM
import Control.Exception
import Data.Set (Set)
import qualified Data.Set as Set
import Data.Foldable (traverse_)

type Job a = IO a

data Pool a = Pool
  { submit     :: Job a -> IO (Either String (Async a))  -- Left if pool closed
  , shutdown   :: IO ()                                  -- graceful
  , shutdownNow:: IO ()                                  -- cancel in-flight
  }

startPool :: Int -> Int -> IO (Pool a)
startPool numWorkers queueSize = do
  q      <- newTBQueueIO queueSize
  closed <- newTVarIO False
  inflight <- newTVarIO Set.empty       -- track Async handles
  workers <- mapM (const asyncWorker) [1..numWorkers]

  let registerA a = atomically $ modifyTVar' inflight (Set.insert (asyncThreadId a))
      unregisterA a = atomically $ modifyTVar' inflight (Set.delete (asyncThreadId a))
      -- Note: asyncThreadId is illustrative; in practice store Async a directly in Set with Ord wrapper.

      submitJob job = atomically $ do
        c <- readTVar closed
        if c then pure (Left "Pool closed")
             else writeTBQueue q job >> pure (Right undefined) -- actual Async created below

  -- worker loop: take job, spawn async that runs job, track it, waitCatch and unregister
  let workerLoop = handle (\(e::SomeException) -> return ()) $ do
        mbJob <- atomically $ do
          c <- readTVar closed
          isEmpty <- isEmptyTBQueue q
          if isEmpty && c then pure Nothing else Just <$> readTBQueue q
        case mbJob of
          Nothing -> return ()
          Just job -> do
            a <- async $ try job >>= \r -> case r of
                     Left (e::SomeException) -> throwIO e -- will be caught below if needed
                     Right v -> return v
            -- track
            atomically $ modifyTVar' inflight (Set.insert a)
            -- wait but don't let exception kill worker; just unregister and continue
            _ <- waitCatch a
            atomically $ modifyTVar' inflight (Set.delete a)
            workerLoop

      asyncWorker = async workerLoop

      submitFn job = do
        ok <- atomically $ do
          c <- readTVar closed
          if c then pure False else writeTBQueue q job >> pure True
        if not ok then pure (Left "Pool closed")
        else do
          -- Not returning per-job Async here to keep API simple. Could instead return Async created by worker.
          pure (Right undefined)

      shutdownFn = do
        atomically $ writeTVar closed True
        -- wait for queue drain and in-flight jobs
        let waitDrain = atomically $ do
              isEmpty <- isEmptyTBQueue q
              inf <- readTVar inflight
              if isEmpty && Set.null inf then pure () else retry
        waitDrain
        traverse_ cancel workers

      shutdownNowFn = do
        atomically $ writeTVar closed True
        inf <- readTVarIO inflight
        traverse_ cancel inf
        traverse_ cancel workers

  pure $ Pool { submit = submitFn, shutdown = shutdownFn, shutdownNow = shutdownNowFn }

Key concepts and choices:- TBQueue bounds the queue to avoid unbounded memory growth.- Workers spawn per-job Asyncs so we can cancel individual jobs; they waitCatch so exceptions in jobs don't kill worker threads.- A TVar tracks in-flight Asyncs for coordinated cancellation.- For graceful shutdown we set a closed flag and wait until queue is empty and in-flight set is empty; then cancel workers.- For immediate shutdown we cancel in-flight Asyncs and workers.

Exception handling and cleanup:- Wrap worker loop with handle to avoid worker termination due to unexpected exceptions.- Use waitCatch on job Asyncs to capture job errors; log or propagate results via an additional result queue if callers need results.- Always cancel worker Asyncs in shutdown to avoid leaks; use bracket or finally at higher level to guarantee pool shutdown.- Be careful storing Async in STM structures—use wrappers with Ord (or store ThreadId or unique Int keys) because Async doesn't have Ord by default.

Improvements / production concerns:- Return per-job Async or an MVar/TVar for job result so callers can await or cancel specific jobs.- Use a proper Ord wrapper (e.g., store Async in TVar (Set Int) using a unique counter).- Use masking/uninterruptibleMask when manipulating critical shared state during shutdown to avoid races.- Add metrics/logging and timeouts for stuck jobs.

This design balances bounded concurrency, explicit cancellation, and safe shutdown while keeping workers resilient to job failures.

HardTechnical

24 practiced

Use GADTs to define a strongly-typed expression AST in Haskell that encodes result types, for example `Expr a` with constructors for integer literals, boolean literals, addition (only for ints), and equality (produces Bool). Implement an evaluator `eval :: Expr a -> a` that is statically guaranteed not to produce type errors.

Sample Answer

Approach: Use a GADT to index Expr by its result type so illegal programs can't be constructed. Each constructor carries the precise result type. Eval is total and type-safe because types are encoded in the AST.

haskell

{-# LANGUAGE GADTs #-}

-- Expr a is an expression that evaluates to a
data Expr a where
  IntLit  :: Int -> Expr Int
  BoolLit :: Bool -> Expr Bool
  Add     :: Expr Int -> Expr Int -> Expr Int
  Eq      :: Eq a => Expr a -> Expr a -> Expr Bool

-- Evaluator: type guarantees result type
eval :: Expr a -> a
eval (IntLit n)    = n
eval (BoolLit b)   = b
eval (Add x y)     = eval x + eval y
eval (Eq x y)      = eval x == eval y

Key points:- GADT syntax (data ... where) ties constructors to precise result types.- Eq constructor requires Eq a so equality is only allowed for comparable types.- The type system prevents malformed trees (e.g., Add (IntLit 1) (BoolLit True) is ill-typed).- Eval is simply structural recursion; no runtime type checks needed.

Example usage:

haskell

expr :: Expr Bool
expr = Eq (Add (IntLit 1) (IntLit 2)) (IntLit 3)

result :: Bool
result = eval expr  -- True

Alternatives/trade-offs:- Could use a sum type for values and a non-indexed AST with runtime checks (less safe).- Extendable to variables and lambda by adding type-indexed environments and higher-rank types.

Unlock Full Question Bank

Get access to hundreds of Haskell & Functional Programming Concepts interview questions and detailed answers.

Join thousands of developers preparing for their dream job.