FP Replica Past Paper 2

Question 1: Higher-Order Functions and Type Classes

(a) What are higher-order functions and why are they so common in Haskell?

Answer: Higher-order functions are functions that take other functions as parameters and/or return functions as results. They’re common in Haskell because:

1. Functions are first-class citizens in Haskell, meaning they can be treated like any other value
2. They enable powerful abstractions and code reuse
3. They facilitate composable program design
4. They’re a natural consequence of the functional programming paradigm
5. They help express algorithms in a clear, concise manner

Higher-order functions like map, filter, and fold are fundamental to Haskell programming as they capture common patterns of computation over data structures.

(b) Define a function twice :: (a -> a) -> a -> a which applies the function (supplied as first parameter) two times to the subsequent parameter value. For instance, twice (+1) 0 would evaluate to 2.

Answer:

twice :: (a -> a) -> a -> a
twice f x = f (f x)

(c) Now consider how to generalize the function twice to a function ntimes, which repeatedly applies a function (supplied as a parameter) multiple times. The type signature is: ntimes :: (a -> a) -> Int -> a -> a. For example, ntimes (+2) 5 0 evaluates to 10 and ntimes tail 3 [1..10] evaluates to [4,5,6,7,8,9,10]. Write a Haskell definition for this ntimes function. You may assume the supplied integer value is non-negative. If the integer value is 0 then the behavior is the same as the identity function.

Answer:

ntimes :: (a -> a) -> Int -> a -> a
ntimes _ 0 x = x
ntimes f n x = ntimes f (n-1) (f x)

(d) Recall that the Functor typeclass is defined as follows:

class Functor f where
   fmap :: (a -> b) -> f a -> f b

Write a Functor instance for the following binary tree data type:

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

Answer

instance Functor Tree where
   fmap _ Leaf = Leaf
   fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

(e) Write a Functor instance for the following data type:

data Either' a b = Left' a | Right' b

Is this a valid Functor instance? Explain why or why not.

Answer

instance Functor (Either' a) where
   fmap _ (Left' x) = Left' x
   fmap f (Right' y) = Right' (f y)

This is a valid Functor instance for Either' a (not for Either' directly). Note that the instance is for the type constructor Either' a which has kind * -> * as required for Functor instances. The function fmap only transforms the value in the Right’ constructor, leaving Left’ values unchanged.

The instance satisfies the functor laws:

6. Identity: fmap id = id
7. Composition: fmap (f . g) = fmap f . fmap g

Question 2: Algebraic Data Types and Pattern Matching

(a) Given the following type and expression:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
 
tree1 :: Tree Int
tree1 = Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3)

Write a function countLeaves :: Tree a → Int that returns the number of Leaf nodes in a tree. For instance, countLeaves tree1 should evaluate to 3.

Answer

countLeaves :: Tree a -> Int
countLeaves (Leaf _) = 1
countLeaves (Branch left right) = countLeaves left + countLeaves right

(b) Write a function mirror :: Tree a -> Tree a that returns the mirror image of a binary tree. For example, if tree1 is Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3), then mirror tree1 would be Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1)).

Answer:

mirror :: Tree a -> Tree a
mirror (Leaf x) = Leaf x
mirror (Branch left right) = Branch (mirror right) (mirror left)

(c) Write a function foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b that generalizes operations over a Tree. The first argument is applied to leaf values, and the second argument combines results from branches.

Answer:

foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f _ (Leaf x) = f x
foldTree f g (Branch left right) = g (foldTree f g left) (foldTree f g right)

(d) Reimplement countLeaves and mirror using foldTree.

Answer:

countLeaves' :: Tree a -> Int
countLeaves' = foldTree (const 1) (+)
 
mirror' :: Tree a -> Tree a
mirror' = foldTree Leaf (\left right -> Branch right left)

(e) Consider a binary search tree (BST) implemented with the following data type:

data BST a = Empty | Node a (BST a) (BST a)

Write a function insert :: Ord a => a -> BST a -> BST a that inserts a value into a BST, maintaining the binary search tree property.

Answer

insert :: Ord a => a -> BST a -> BST a
insert x Empty = Node x Empty Empty
insert x (Node y left right)
   | x < y     = Node y (insert x left) right
   | x > y     = Node y left (insert x right)
   | otherwise = Node x left right  -- Replace existing value

Question 3: Monads and Effects

(a) The State monad allows for stateful computations while maintaining referential transparency. It is defined as follows:

newtype State s a = State { runState :: s -> (a, s) }
 
instance Monad (State s) where
   return x = State $ \s -> (x, s)
   m >>= f = State $ \s -> 
               let (a, s') = runState m s
               in runState (f a) s'

Define the following helper functions for the State monad:

get :: State s s            -- Retrieves the current state
put :: s -> State s ()      -- Replaces the state
modify :: (s -> s) -> State s ()  -- Applies a function to the state

Answer

get :: State s s
get = State $ \s -> (s, s)
 
put :: s -> State s ()
put s = State $ \_ -> ((), s)
 
modify :: (s -> s) -> State s ()
modify f = State $ \s -> ((), f s)

(b) Use the State monad to implement a function evalRPN that evaluates a Reverse Polish Notation expression. RPN expressions are represented as lists of tokens, where a token can be either a number or an operator (+, -, _, /). For example, evalRPN [5, 3, "+", 2, "_"] should evaluate to 16.

data Token = Number Int | Plus | Minus | Times | Divide
 
evalRPN :: [Token] -> Maybe Int

Answer

import Control.Monad.State
 
data Token = Number Int | Plus | Minus | Times | Divide
   deriving (Show, Eq)
 
type Stack = [Int]
 
evalRPN :: [Token] -> Maybe Int
evalRPN tokens = 
   case evalState (processTokens tokens) [] of
       [result] -> Just result
       _        -> Nothing
 
processTokens :: [Token] -> State Stack Stack
processTokens [] = get
processTokens (token:rest) = do
   modify (processToken token)
   processTokens rest
 
processToken :: Token -> Stack -> Stack
processToken (Number n) stack = n : stack
processToken Plus (b:a:rest) = (a + b) : rest
processToken Minus (b:a:rest) = (a - b) : rest
processToken Times (b:a:rest) = (a * b) : rest
processToken Divide (b:a:rest) = (a `div` b) : rest
processToken _ stack = stack  -- Error case, should never happen with valid input

(c) Consider a simple game where a player moves on a grid. The player’s state consists of their position (x, y) and their score. Implement the following functions using the State monad:

type PlayerState = ((Int, Int), Int)  -- ((x, y), score)
 
moveUp :: State PlayerState ()
moveDown :: State PlayerState ()
moveLeft :: State PlayerState ()
moveRight :: State PlayerState ()
addPoints :: Int -> State PlayerState ()

Answer:

type PlayerState = ((Int, Int), Int)  -- ((x, y), score)
 
moveUp :: State PlayerState ()
moveUp = modify (\((x, y), score) -> ((x, y+1), score))
 
moveDown :: State PlayerState ()
moveDown = modify (\((x, y), score) -> ((x, y-1), score))
 
moveLeft :: State PlayerState ()
moveLeft = modify (\((x, y), score) -> ((x-1, y), score))
 
moveRight :: State PlayerState ()
moveRight = modify (\((x, y), score) -> ((x+1, y), score))
 
addPoints :: Int -> State PlayerState ()
addPoints pts = modify (\(pos, score) -> (pos, score + pts))

(d) Consider a function getElement :: [a] → Int → Maybe a that safely accesses an element in a list at a given index. Using the Maybe monad, write a function getElementsSum that takes a list of integers and a list of indexes, and returns the sum of the elements at those indexes. If any index is out of bounds, the function should return Nothing.

Answer:

getElement :: [a] -> Int -> Maybe a
getElement xs i
   | i >= 0 && i < length xs = Just (xs !! i)
   | otherwise = Nothing
 
getElementsSum :: [Int] -> [Int] -> Maybe Int
getElementsSum xs indices = do
   elements <- mapM (getElement xs) indices
   return (sum elements)

Alternatively:

getElementsSum :: [Int] -> [Int] -> Maybe Int
getElementsSum xs indices = fmap sum $ sequence $ map (getElement xs) indices

Question 4: Lazy Evaluation and Infinite Data Structures

(a) Explain the concept of lazy evaluation in Haskell and how it differs from eager evaluation.

Answer: Lazy evaluation is a strategy where expressions are evaluated only when their values are needed. In Haskell, this means:

1. Expressions are not evaluated when they are bound to variables, but only when their results are required
2. Function arguments are not evaluated before the function is called
3. Data structures are constructed on-demand - only the parts that are accessed are computed

This differs from eager evaluation (used in most programming languages) where:

4. Expressions are evaluated immediately when they are bound
5. Function arguments are fully evaluated before the function is called
6. Data structures are completely constructed at definition time

Benefits of lazy evaluation include:

• Ability to work with infinite data structures
• Potential performance improvements by avoiding unnecessary computation
• More modular code through separation of data structure generation and consumption
• Natural implementation of control structures as functions

Challenges include:

• Less predictable space usage due to unevaluated expressions (thunks)
• Harder to reason about performance

representing the Fibonacci sequence [0, 1, 1, 2, 3, 5, 8, ...] using lazy evaluation.

Answer:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

I’ll continue with the rest of the Replica Past Paper 2.

that returns an infinite list of prime numbers using the Sieve of Eratosthenes algorithm.

Answer:

primes :: [Integer]
primes = sieve [2..]
 where
   sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

(d) Consider the following definition of an infinite binary tree:

data InfTree a = Node a (InfTree a) (InfTree a)
 
-- Creates an infinite tree where each node contains its path
-- represented as a list of Bools (False = left, True = right)
pathTree :: InfTree [Bool]
pathTree = buildTree []
 where
   buildTree path = Node path 
                      (buildTree (path ++ [False])) 
                      (buildTree (path ++ [True]))

Write a function getPath :: [Bool] → InfTree [Bool] → [Bool] that retrieves the node value at the path specified by the first argument. For example, getPath [False, True] pathTree should return [False, True].

Answer

getPath :: [Bool] -> InfTree [Bool] -> [Bool]
getPath [] (Node val _ _) = val
getPath (False:ps) (Node _ left _) = getPath ps left
getPath (True:ps) (Node _ _ right) = getPath ps right

(e) Write a function takeLevel :: Int -> InfTree a -> [a] that returns all values at a specific depth in the tree, from left to right. For example, takeLevel 0 pathTree should return [[]], and takeLevel 1 pathTree should return [[False], [True]].

Answer:

takeLevel :: Int -> InfTree a -> [a]
takeLevel 0 (Node val _ _) = [val]
takeLevel n (Node _ left right) = takeLevel (n-1) left ++ takeLevel (n-1) right

(f) Consider the following infinite data structure representing a game tree for tic-tac-toe:

data Player = X | O deriving (Show, Eq)
type Board = [[Maybe Player]]  -- 3x3 grid
data GameTree = GameTree Board Player [GameTree]

Explain how lazy evaluation makes it possible to define such a tree, and how pruning strategies can be implemented to explore only parts of the tree.

Answer

Lazy evaluation allows us to define the complete game tree for tic-tac-toe without requiring it to be fully computed in memory at once. The tree can potentially contain all possible game states, but only the paths that are actually explored will be computed.

When we define the game tree, we’re actually defining a recipe for how to generate each node when needed, not the entire tree structure in memory. The nodes and branches are only calculated when we attempt to access them.

Pruning strategies can be implemented by defining functions that traverse the tree but only follow certain branches based on evaluation criteria:

1. Alpha-beta pruning can avoid exploring branches that won’t affect the final decision
2. We can implement a depth-limited search that only explores the tree to a certain depth
3. Heuristic evaluations can help decide which branches are worth exploring

For example, a minimax algorithm with alpha-beta pruning would avoid evaluating branches that can’t possibly affect the final decision. Since the tree is lazily evaluated, branches that are never accessed are never computed, saving both time and memory.

This combination of lazy evaluation and pruning strategies allows us to work with a conceptually infinite game tree while only computing the relevant portions of it.