FP Replica Past Paper 1

Question 1: Types and Functions

(a) Give the type of f1, explain what the type means, and give the value of test_f1, where the definitions are:

f1 :: (Num a, Eq a) => a -> [a] -> [a]
f1 k xs = [x+k | x <- xs, x /= k]
test_f1 = f1 3 [2, 3, 4, -1, 5, 3]

Answer

f1 :: (Num a, Eq a) => a -> [a] -> [a]

The type means that the function takes two arguments: a value of type a and a list whose elements have type a; a can be any type provided that it is in both the Num class (so arithmetic operations can be performed) and the Eq class (so equality comparisons can be done). The function returns a list of the same type.

Value of test_f1: [5, 7, 2, 8]

(b) Give the type of f2 and the value of test_f2:

f2 f g h x = f (g (h x))
test_f2 = f2 (*2) (+3) (^2) 4

Answer

f2 :: (c -> d) -> (b -> c) -> (a -> b) -> a -> d

Value of test_f2: 2 * (3 + (4^2)) = 2 * (3 + 16) = 2 * 19 = 38

(c) Explain why head and tail are considered unsafe functions. Define safer total versions safeHead :: [a] -> Maybe a and safeTail :: [a] -> Maybe [a] using the Maybe monad.

Answer: head and tail are considered unsafe because they are partial functions - they’re undefined when applied to an empty list. If either is called with an empty list, it results in a runtime error.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
 
safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (_:xs) = Just xs

(d) Consider a list fibSeq :: [Integer] with value [1, 1, 2, 3, 5, 8, 13, ...] which is infinitely long. Write a definition of fibSeq and explain how lazy evaluation makes this possible.

Answer:

fibSeq :: [Integer]
fibSeq = 1 : 1 : zipWith (+) fibSeq (tail fibSeq)

Lazy evaluation makes this possible because expressions are only evaluated when their values are needed. The definition is recursive, but Haskell only computes as many elements as required when the list is used. Without lazy evaluation, the program would attempt to compute an infinite list eagerly, resulting in non-termination or memory exhaustion.

(e) Write a function allPairs :: [a] -> [b] -> [(a,b)] that computes the Cartesian product of two lists. For instance, allPairs "hi" [1,2,3] should evaluate to [('h',1), ('h',2), ('h',3), ('i',1), ('i',2), ('i',3)]

Answer:

allPairs :: [a] -> [b] -> [(a,b)]
allPairs xs ys = [(x,y) | x <- xs, y <- ys]
 
-- Alternative implementation:
-- allPairs xs ys = concatMap (\x -> map (\y -> (x,y)) ys) xs

Question 2: Monads and Algebraic Data Types

(a) Define an algebraic data type called Shape. A Shape value can be either a Circle with a radius, a Rectangle with width and height, or a Triangle with three side lengths. All dimensions should be of type Double.

Answer:

data Shape = Circle Double
         | Rectangle Double Double
         | Triangle Double Double Double
         deriving (Show, Eq)

(b) Write a function area :: Shape -> Double that calculates the area of a given Shape.

Answer:

area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
area (Triangle a b c) = 
   let s = (a + b + c) / 2  -- semi-perimeter
   in sqrt (s * (s-a) * (s-b) * (s-c))  -- Heron's formula

(c) Write a smart constructor mkTriangle :: Double → Double → Double → Maybe Shape that ensures the three sides can form a valid triangle (each side must be positive and the sum of any two sides must be greater than the third side).

Answer:

mkTriangle :: Double -> Double -> Double -> Maybe Shape
mkTriangle a b c
   | a <= 0 || b <= 0 || c <= 0 = Nothing
   | a + b <= c || a + c <= b || b + c <= a = Nothing
   | otherwise = Just (Triangle a b c)

(d) Consider the Maybe monad. Give the type signature and implementation of the >>= (bind) operator for this monad, and explain how it handles failure propagation.

Answer:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x

The >>= operator for Maybe handles failure propagation by short-circuiting computation when a Nothing is encountered. If the left argument is Nothing, the result is immediately Nothing without evaluating the function f. If the left argument is Just x, the function f is applied to x. This allows a series of computations that might fail to be chained together, with failure at any step immediately propagating to the final result.

(e) Rewrite the following code using do notation:

validateAndProcess :: Int -> Maybe String
validateAndProcess x =
   checkPositive x >>= \y ->
   checkEven y >>= \z ->
   return (show (z * 2))
 
checkPositive :: Int -> Maybe Int
checkPositive x = if x > 0 then Just x else Nothing
 
checkEven :: Int -> Maybe Int
checkEven x = if even x then Just x else Nothing

Answer

validateAndProcess :: Int -> Maybe String
validateAndProcess x = do
   y <- checkPositive x
   z <- checkEven y
   return (show (z * 2))

Question 3: Equational Reasoning and Functional Composition

(a) Prove that map f (filter p xs) = filter p (map f xs) is false in general by providing a counterexample.

Answer: The equation map f (filter p xs) = filter p (map f xs) is false in general. A counterexample:

Let’s use f = (*2) and p = (>3) and xs = [1,2,3]

Left side: map f (filter p xs) = map (*2) (filter (>3) [1,2,3]) = map (*2) [] = []

Right side: filter p (map f xs) = filter (>3) (map (*2) [1,2,3]) = filter (>3) [2,4,6] = [4,6]

Since [] ≠ [4,6], the equation does not hold in general.

(b) Assume that the list xs has a finite (but unbounded) number of elements. Prove that sum (map (2*) xs) = 2 * sum xs using the following definition of sum:

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

Answer

Proof by induction over xs.

Base case: xs = [] sum (map (2*) []) = sum [] = 0 = 2*0 = 2 * sum []

Induction case: Assume sum (map (2*) xs) = 2 * sum xs holds for some xs.

Consider x:xs: sum (map (2*) (x:xs)) = sum ((2_x) : map (2_) xs) = (2_x) + sum (map (2_) xs) = (2*x) + 2 * sum xs (by induction hypothesis) = 2 * (x + sum xs) (by distributivity) = 2 * sum (x:xs) (by definition of sum)

Therefore, sum (map (2*) xs) = 2 * sum xs for all finite lists xs.

(c) Recall that the monadic bind operator for the IO monad has type (>>=) :: IO a -> (a -> IO b) -> IO b. Explain what this type signature means in terms of sequencing IO operations.

Answer: The bind operator for the IO monad allows sequencing of IO operations where the result of one operation is used to determine the next operation.

The type signature (>>=) :: IO a → (a → IO b) → IO b indicates that:

1. We start with an IO action that, when performed, will produce a value of type a
2. We provide a function that, given a value of type a, determines the next IO action to perform
3. The result is a composite IO action that first performs the initial action, then uses its result to determine and perform the next action

This allows operations to be sequenced in a way that respects their dependencies, and it ensures that side effects occur in a well-defined order, which is crucial for I/O operations.

(d) Simplify the following lambda expression. Show each step in the reduction, and for each step show which conversion rule you are using.

(\a -> (\b -> a (b b))) (\x -> x) (\y -> y+1) 2

Answer

(\a -> (\b -> a (b b))) (\x -> x) (\y -> y+1) 2 > beta [substitute a = (\x → x)] (\b → (\x → x) (b b)) (\y → y+1) 2 > beta [substitute b = (\y → y+1)] (\x → x) ((\y → y+1) (\y → y+1)) 2 > beta [apply inner function] (\x → x) ((\y → y+1) + 1) 2 > beta [apply increment] (\x → x) (2 + 1) 2 > arithmetic (\x → x) 3 2 > beta [substitute x = 3] 3 2 ~> type error (cannot apply 3 to 2)`

Note: There’s actually a type error in this expression. The result of (\y -> y+1) (\y -> y+1) doesn’t make sense because we’re trying to apply a function that expects a number to another function.

Question 4: Domain Specific Languages and Parsers

(a) Define the term embedded domain specific language (EDSL). Give three examples of Haskell features that are useful for implementing EDSLs, and explain why they are useful.

Answer: An embedded domain specific language (EDSL) is a language designed for a specific application domain that is implemented by embedding it within a general-purpose host language (like Haskell). Instead of building a separate compiler or interpreter, an EDSL leverages the host language’s infrastructure and tools.

Three Haskell features useful for implementing EDSLs:

1. Algebraic data types: Enable the definition of custom data structures that model domain-specific concepts precisely and type-safely.

2. Type classes: Allow customization of standard operations for domain-specific types, making the EDSL syntax more natural. They enable operator overloading and polymorphism.

3. Higher-order functions: Facilitate the creation of combinators that compose smaller domain-specific operations into larger ones, allowing for a declarative programming style.

Other valuable features include lazy evaluation (for defining potentially infinite structures), monads (for building custom control flow), and custom operators (for domain-specific notation).

(b) Consider a type Color defined as follows:

data Color = Red | Green | Blue | Yellow | Purple | Custom Int Int Int

Write a function blend :: Color → Color → Color that blends two colors according to these rules:

• Blending primary colors (Red, Green, Blue) creates secondary colors (Yellow, Purple, Cyan)
• Blending a primary color with itself returns the same color
• Blending Custom colors averages their RGB components
• Other combinations result in a suitable Custom color

Answer

blend :: Color -> Color -> Color
blend Red Green = Yellow
blend Green Red = Yellow
blend Red Blue = Purple
blend Blue Red = Purple
blend Green Blue = Cyan
blend Blue Green = Cyan
blend Red Red = Red
blend Green Green = Green
blend Blue Blue = Blue
blend (Custom r1 g1 b1) (Custom r2 g2 b2) = 
   Custom ((r1 + r2) `div` 2) ((g1 + g2) `div` 2) ((b1 + b2) `div` 2)
blend c1 c2 = 
   let (r1, g1, b1) = toRGB c1
       (r2, g2, b2) = toRGB c2
   in Custom ((r1 + r2) `div` 2) ((g1 + g2) `div` 2) ((b1 + b2) `div` 2)
 
toRGB :: Color -> (Int, Int, Int)
toRGB Red = (255, 0, 0)
toRGB Green = (0, 255, 0)
toRGB Blue = (0, 0, 255)
toRGB Yellow = (255, 255, 0)
toRGB Purple = (255, 0, 255)
toRGB Cyan = (0, 255, 255)
toRGB (Custom r g b) = (r, g, b)

(c) Using the Parsec library, write a parser for a simple language of arithmetic expressions that supports addition, subtraction, multiplication, division, and parentheses. The parser should return an abstract syntax tree represented by the following data type:

data Expr = Num Int
         | Add Expr Expr
         | Sub Expr Expr
         | Mul Expr Expr
         | Div Expr Expr
         deriving (Show)

Answer

import Text.Parsec
import Text.Parsec.String
import Text.Parsec.Expr
import Text.Parsec.Token
import Text.Parsec.Language
 
expr :: Parser Expr
expr = buildExpressionParser table term
 
term :: Parser Expr
term = parens expr <|> fmap Num number
 
table = [ [binary "*" Mul AssocLeft, binary "/" Div AssocLeft]
       , [binary "+" Add AssocLeft, binary "-" Sub AssocLeft]
       ]
 
binary name fun assoc = 
 Infix (do{ reservedOp name; return fun }) assoc
 
TokenParser { parens = parens
           , reservedOp = reservedOp
           , number = number
           , whiteSpace = whiteSpace
           } = makeTokenParser emptyDef
 
parseExpr :: String -> Either ParseError Expr
parseExpr = parse (whiteSpace >> expr) ""

(d) Write an evaluator for the expression language defined in part (c). The evaluator should handle division by zero by returning a Maybe type.

Answer:

eval :: Expr -> Maybe Int
eval (Num n) = Just n
eval (Add e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 + v2)
eval (Sub e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 - v2)
eval (Mul e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 * v2)
eval (Div e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   if v2 == 0 
      then Nothing
      else Just (v1 `div` v2)