FP 8.1

What is a pure function in Haskell?

A pure function always returns the same output for the same input and has no side‑effects (it cannot modify state, print, read files, etc.).

What is a monad?

A monad is a design pattern (type class) that allows sequencing of computations while managing side‑effects in a controlled way. It provides two main operations: pure (or return) and >>= (bind).

What does the pure function do?

pure takes a plain value and lifts it into the monadic context. For example, pure x = [x] for the list monad, pure x = Just x for the Maybe monad.

What does the >>= (bind) operator do?

bind (>>=) takes a monadic value m a and a function a -> m b, and returns a new monadic value m b. It sequences the computation by extracting the value from the first monad and applying the function.

How does do‑notation desugar to >>=?

do { x

What is the Maybe monad used for?

The Maybe monad models computations that may fail. It automatically propagates Nothing (failure) through a sequence of operations.

What is the List monad used for?

The List monad models non‑deterministic computations that can produce zero, one, or multiple results.

What is the IO monad used for?

The IO monad is used for computations that perform input/output operations, such as printing to the screen or reading from a file.

What is the Writer monad used for?

The Writer monad allows a computation to produce a log (e.g., a list of messages) alongside its main result.

What is the State monad used for?

The State monad simulates mutable state of type s while producing a result of type a.

Write the type signature of fmap.

fmap :: (a -> b) -> f a -> f b

Write the type signature of pure.

pure :: a -> f a

Write the type signature of (

(

Write the type signature of return.

return :: a -> m a (same as pure)

Write the type signature of (>>=).

(>>=) :: m a -> (a -> m b) -> m b

What is the relationship between return and pure?

return = pure; they are the same operation.

How is the Functor instance for Maybe defined?

fmap g Nothing = Nothing; fmap g (Just x) = Just (g x)

How is the Applicative instance for Maybe defined?

pure x = Just x; Nothing <> _ = Nothing; Just g <> xm = fmap g xm

How is the Monad instance for Maybe defined?

Nothing >>= f = Nothing; Just x >>= f = f x

How is the Functor instance for lists defined?

fmap = map

How is the Applicative instance for lists defined?

pure x = [x]; gs

How is the Monad instance for lists defined?

xs >>= f = [y | x <- xs, y <- f x]

Write the desugaring of do { x

m >>= \x -> n >>= \y -> pure (x + y)

What does the modify function do in the State monad?

modify f updates the state by applying function f to it, and returns () as the result.

What does the get function do in the State monad?

get returns the current state as the result, leaving the state unchanged.

What does the put function do in the State monad?

put s replaces the current state with s, returning ().

How do you extract a value from the Writer monad?

Use runWriter :: Writer w a -> (a, w) to obtain the result and the log.

How do you extract a value from the State monad?

Use runState :: State s a -> s -> (a, s) to obtain the result and the final state after starting with an initial state.

What is a parser?

A parser is a program that takes a string of characters as input and produces a structured representation (like a tree) that makes the syntactic structure explicit.

Define the Parser type used in the notes.

newtype Parser a = P (String -> [(a, String)])

What does the parse function do?

parse (P p) inp = p inp; it applies a parser to an input string.

What does the item parser do?

item consumes one character from the input; if the input is empty it fails (returns []), otherwise it returns the first character and the remaining string as a singleton list.

What does the sat parser do?

sat p succeeds on a character that satisfies predicate p; it uses item and checks the condition, failing with empty if the condition fails.

How do you create a parser that always succeeds with a value v without consuming input?

pure v = P (\inp -> [(v, inp)])

What does the

What does empty do for parsers?

empty = P (\inp -> []), a parser that always fails.

What does many p do?

many p applies parser p zero or more times, collecting the results in a list.

What does some p do?

some p applies parser p one or more times, collecting the results in a list.

How do you parse an identifier (variable name) in the given parser library?

ident = do { x <- lower; xs <- many alphanum; pure (x:xs) }

How do you parse a natural number?

nat = do { xs <- some digit; pure (read xs) }

How do you parse an integer (including negative numbers)?

int = (do { char '-'; n

What is the purpose of the token parser?

token p ignores any surrounding spaces before and after applying parser p.

What does the expression parser expr do?

expr parses addition and subtraction with precedence and associativity; it first parses a term, then optionally a '+' and another expression.

What does the term parser do?

term parses multiplication; it first parses a factor, then optionally a '*' and another term.

What does the factor parser do?

factor parses either a number or an expression inside parentheses.

What is the type of the eval function?

eval :: String -> Int; it parses and evaluates an arithmetic expression, handling errors.

What is the key advantage of using the Maybe monad for error handling?

It automatically propagates Nothing without needing explicit case analysis at every step.

How does the list monad handle failure?

An empty list [] represents failure; a singleton list represents success; multiple results represent non‑determinism.

How does do‑notation with lists correspond to list comprehensions?

do { x <- xs; y <- ys; pure (x + y) } is equivalent to [ x + y | x <- xs, y <- ys ].

What is the difference between Writer and State?

Writer accumulates a log (monoid) without explicit state transitions; State manages a mutable value that can be read and written.

What does the tell function do in the Writer monad?

tell w adds w to the log.

What does the modify function do in the State monad?

modify f applies function f to the current state and updates it.

What is the type of runWriter?

runWriter :: Writer w a -> (a, w)

What is the type of runState?

runState :: State s a -> s -> (a, s)

What is the purpose of the Monad type class?

It defines the >>= operation and requires that instances also be Applicative and Functor.

What are the three laws that monads must satisfy?

Left identity: return a >>= f = f a; Right identity: m >>= return = m; Associativity: (m >>= f) >>= g = m >>= (\x -> f x >>= g)

What does the phrase "monad is a design pattern" mean?

It means that many different types (Maybe, [], IO, etc.) share a common structure and set of operations that allow them to be used in a uniform way.

What is the difference between pure and return?

They are identical; pure comes from Applicative, return from Monad; return is often defined as pure.

Why are monads useful in Haskell?

They allow pure functions to interact with side‑effects in a controlled, type‑safe way, preserving referential transparency.

How does the State monad implement mutable state?

It represents a computation as a function from an initial state to a result and a new state, and >>= composes these functions.

What is the type of the State constructor in the notes?

newtype State s a = State (s -> (a, s))

What is the role of the Functor class in relation to Monad?

Every Monad must be an Applicative, and every Applicative must be a Functor; thus Monad provides fmap via the Functor instance.

What does (

It applies a function inside a context to a value inside a context; for Maybe, it applies the function if both are Just, else Nothing.

What does fmap do?

It applies a function to a value inside a functorial context; for lists it's map, for Maybe it's applying to the inside of Just.

Write the definition of the Monad instance for Writer' (the custom version).

return x = Result x ""; (Result x s) >>= f = case f x of Result y t -> Result y (s ++ t)

Write the definition of the Monad instance for State' (the custom version).

return x = T (\u -> (x,u)); (T p) >>= f = T (\u -> case p u of (x,v) -> case f x of T q -> q v)

What is the purpose of the token parser?

It ignores leading and trailing spaces before and after applying the given parser.

What is the grammar for arithmetic expressions used in the parsing section?

expr = term '+' expr | term; term = factor '*' term | factor; factor = '(' expr ')' | nat

What does the string parser do?

string xs parses the exact sequence of characters xs, returning xs as the result.

What is the difference between many and some?

many allows zero or more occurrences; some requires at least one occurrence.

How do you combine parsers sequentially in do‑notation?

Use do { x <- parser1; y <- parser2; pure (f x y) } to run parser1, then parser2, and combine their results.

What is the significance of the return type being a list of pairs in the Parser definition?

The list allows for multiple possible parses (ambiguity) and empty list indicates failure; each pair is (result, remaining input).

Why is newtype used instead of data for Parser?

newtype has no runtime overhead; it is just a wrapper around the underlying function type.