Namespace LogoNamespace0.3L
cs140pythoncs141csswebdevhtmlalgorithmsmathethics

  Guide

CS141 Specimen Paper

Tue Sep 27 2022

My solutions to the 2022 CS141 Specimen Paper. Find the original pdf at https://warwick.ac.uk/fac/sci/dcs/teaching/material/cs141/cs1410-specimen.pdf. Parts of Question 3 and of Question 6 are left out.

Question 1
This question is about the fundamentals ofprogramming in Haskell.\textbf{This question is about the fundamentals of} \newline \textbf{programming in Haskell.}
(a) For each term, first desugar it, then evaluate it as far as possible.Give all intermediate steps of the evaluation.\text{(a) For each term, first desugar it, then evaluate it as far as possible.} \newline \text{Give all intermediate steps of the evaluation.}
Alex covered this in the revision lecture, so I won't go over it again.
(b) Describe the usage of the (.) combinator in typical Haskell code. A definition of (.) is given in the Appendix\text{(b) Describe the usage of the \texttt{(.)} combinator in typical Haskell code.} \newline \text{ A definition of \texttt{(.)} is given in the Appendix}
(.) is a right-associative infix operator of type(b -> c) -> (a -> b) -> (a -> c) which describes functioncomposition. We can compose two functions f and g as f.g, normallydenoted f(g(x)) in mathematics. Example usage is given below.\text{\texttt{(.)} is a right-associative infix operator of type} \newline \text{\texttt{(b -> c) -> (a -> b) -> (a -> c)} which describes function} \newline \text{composition. We can compose two functions \texttt{f} and \texttt{g} as \texttt{f.g}, normally} \newline \text{denoted \texttt{f(g(x))} in mathematics. Example usage is given below.}
  haskell  
-- returns the second successor
succ2 :: Ord a => a -> a
succ2 = succ . succ
(c) (...) Define an equivalent function concatMap’ in terms of a single callto foldr with suitable arguments so that it is implicitly recursive.\text{(c) (...) Define an equivalent function \texttt{concatMap'} in terms of a single call} \newline \text{to foldr with suitable arguments so that it is implicitly recursive.}
  haskell  
concatMap' :: (a -> [b]) -> [a] -> [b]
concatMap' f = foldr (\x ys -> f x ++ ys) []
(d) Each of the following expressions is polymorphic. For each expression,give two distinct monomorphic typings. All functions used are listedin the Appendix.\text{(d) Each of the following expressions is polymorphic. For each expression,} \newline \text{give two distinct monomorphic typings. All functions used are listed} \newline \text{in the Appendix.}
  haskell  
-- (i) 
5 :: Int
5 :: Integer

-- (ii)
(\x y z -> y) :: () -> () -> () -> ()
(\x y z -> y) :: () -> Int -> () -> Int

-- (iii)
(minimum $ pure $ pure False) :: [Bool]
(minimum $ pure $ pure False) :: Maybe Bool

--- (iv)
null :: [Int] -> Bool
null :: [Double] -> Bool
Question 2
This question is about recursive and higher-order functions.\textbf{This question is about recursive and higher-order functions.}
(a) Define a function isPrime :: Integer -> Bool which given aninteger value, determines whether it is a prime number.\text{(a) Define a function \texttt{isPrime :: Integer -> Bool} which given an} \newline \text{integer value, determines whether it is a prime number.}
  haskell  
isPrime :: Integer -> Bool
isPrime 1 = False
isPrime n = not $ any (== 0) [ x `mod` n | x <- [2..n] ]
(b) Using a list comprehension and isPrime, write a definitionof primes :: [Integer] which constructs the infinite listof prime numbers.\text{(b) Using a list comprehension and isPrime, write a definition} \newline \text{of \texttt{primes :: [Integer]} which constructs the infinite list} \newline \text{of prime numbers.}
  haskell  
primes :: [Integer]
primes = [ x | x <- [2..], isPrime x ]
(c) (i) Using your answer to (b), write a functiontoPrime :: Char -> Integer which maps each character inthe alphabet to a unique prime number, ignoring capitalisation. \text{(c) (i) Using your answer to (b), write a function} \newline \text{\texttt{toPrime :: Char -> Integer} which maps each character in} \newline \text{the alphabet to a unique prime number, ignoring capitalisation. }
  haskell  
toPrime :: Char -> Integer
toPrime = (primes !!) . ord . toLower
(c) (ii) With the help of toPrime, define a functionscore :: String -> Integer which calculates the product of allthe corresponding prime numbers for the characters in the input string.\text{(c) (ii) With the help of \texttt{toPrime}, define a function} \newline \text{\texttt{score :: String -> Integer} which calculates the product of all} \newline \text{the corresponding prime numbers for the characters in the input string.}
  haskell  
score :: String -> Integer
score = product . map toPrime
(c) (iii) With the help of score, define a function isAnagram :: String -> String -> Bool which determineswhether two String values are anagrams of each other.\text{(c) (iii) With the help of score, define a function} \newline \text{ \texttt{isAnagram :: String -> String -> Bool} which determines} \newline \text{whether two String values are anagrams of each other.}
  haskell  
isAnagram :: String -> String -> Bool
isAnagram = (==) `on` score -- import Data.Function (on)
(c) (iv) With the help of the previous definitions, define a functionanagrams :: [String] -> [(String, [String])] which, givena list of String values representing a list of words, returns a list ofpairs, of the same length, in which every input word is pairedwith a list of all its anagrams found in the input (except itself). \text{(c) (iv) With the help of the previous definitions, define a function} \newline \text{\texttt{anagrams :: [String] -> [(String, [String])]} which, given} \newline \text{a list of String values representing a list of words, returns a list of} \newline \text{pairs, of the same length, in which every input word is paired} \newline \text{with a list of all its anagrams found in the input (except itself). }
  haskell  
anagrams :: [String] -> [(String, [String])]
anagrams xs = map (\x -> (x, [ t | t <- (xs \\ [x]), isAnagram x t ])) cs
(c) (v) With the help of the previous definitions, define a function subgrams :: [String] -> [(String, [String])] which behaveslike anagrams, except it also includes words which do not useevery character from the original word. \text{(c) (v) With the help of the previous definitions, define a function} \newline \text{ \texttt{subgrams :: [String] -> [(String, [String])]} which behaves} \newline \text{like anagrams, except it also includes words which do not use} \newline \text{every character from the original word. }
  haskell  
subgrams :: [String] -> [(String, [String])]
subgrams xs = map (\x -> (x, [t | t <- (xs \\ [x]), isSubgram t x ])) xs
                 where isSubgram n m = score m `mod` score n == 0
Question 3
(b) The semantics of (Report) Haskell include three principal formsof polymorphism. Name the two forms which specifically relate totype classes.\text{(b) The semantics of (Report) Haskell include three principal forms} \newline \text{of polymorphism. Name the two forms which specifically relate to} \newline \text{type classes.}
Ad-Hoc Polymorphism and Subtype Polymorphism
(c) Declare a type class called Default, which describes, for anyimplementing type a, a value called def of type a.\text{(c) Declare a type class called \texttt{Default}, which describes, for any} \newline \text{implementing type \texttt{a}, a value called \texttt{def} of type \texttt{a}.}
Question 4
This question is about data structures.\textbf{This question is about data structures.}
(a) Use record syntax to give a suitable polymorphic definitionfor the Tape data type\text{(a) Use record syntax to give a suitable polymorphic definition} \newline \text{for the \texttt{Tape} data type}
  haskell  
data Tape a = Tape {
   ls :: [a],
   focus :: a,
   rs :: [a]
}
(b) Define singleton :: a -> Tape a, which is a tape with a single value.\text{(b) Define \texttt{singleton :: a -> Tape a}, which is a tape with} \newline \text{ a single value.}
  haskell  
singleton :: a -> Tape a
singleton x = Tape [] x []
(c) Define moveLeft :: Tape a -> Tape a, which moves the focusof the tape one element to the left if (and only if) the left sublistis nonempty. If it is empty, the tape should remain unchanged.\text{(c) Define \texttt{moveLeft :: Tape a -> Tape a}, which moves the focus} \newline \text{of the tape one element to the left if (and only if) the left sublist} \newline \text{is nonempty. If it is empty, the tape should remain unchanged.}
  haskell  
moveLeft :: Tape a -> Tape a
moveLeft t@(Tape [] _ _) = t
moveLeft (Tape (x:xs) f rs) = Tape xs x (f:rs)
(d) Define a function fromList, which converts a list into a Tape if possible.You should choose an appropriate type for fromList; ensure thatyour function is total.\text{(d) Define a function fromList, which converts a list into a \texttt{Tape} if possible.} \newline \text{You should choose an appropriate type for \texttt{fromList}; ensure that} \newline \text{your function is total.}
  haskell  
fromList :: [a] -> Tape a
fromList (x:xs) = Tape [] x xs
fromList [] = error "Empty list cannot be converted to a Tape"
(f) Tape can be folded. Define a suitable Foldable instance for Tape\text{(f) \texttt{Tape} can be folded. Define a suitable Foldable instance for \texttt{Tape}}
  haskell  
instance Foldable Tape where
   -- foldr :: (a -> b -> b) -> b -> t a -> b
   foldr f z (Tape ls fc rs) = foldr f (f fc foldedLs) rs
                                 where foldedLs = foldr f z ls
(g) Define a functionsplitAt :: (a -> Bool) -> Tape a -> ([a], [a]) (...)\text{(g) Define a function} \newline \text{\texttt{splitAt :: (a -> Bool) -> Tape a -> ([a], [a])} (...)}
  haskell  
splitAt :: (a -> Bool) -> Tape a -> ([a], [a])
splitAt f = (\t -> (reverse $ ls t, rs t)) . until (f . focus) moveRight . toLeft
Question 5
This question is about functors, applicative functors,and monads.\textbf{This question is about functors, applicative functors,} \newline \textbf{and monads.}
(a) The Functor, Applicative and Monad type classes form part ofthe type class hierarchy. What is the type class hierarchy? Describethe subtype relationships between these three type classes.\text{(a) The Functor, Applicative and Monad type classes form part of} \newline \text{the type class hierarchy. What is the type class hierarchy? Describe} \newline \text{the subtype relationships between these three type classes.}
Monad is a subtype of Applicative, which is a subtype of Functor. Monad is older than Applicative, and it's return function is identical to Applicative's pure function beyond the typeclass constraints.
(b) State s is a functor. Give a suitable Functor instance for State s. \text{(b) \texttt{State s} is a functor. Give a suitable Functor instance for \texttt{State s}. }
  haskell  
instance Functor (State s) where
   -- fmap :: (a -> b) -> State s a -> State s b
   fmap f st = State $ \s -> let (x, y) = runState st $ s in (f x, y)
(c) State s is an applicative functor. Give a suitable Applicativeinstance for State s.\text{(c) \texttt{State s} is an applicative functor. Give a suitable \texttt{Applicative}} \newline \text{instance for \texttt{State s}.}
  haskell  
instance Applicative (State s) where
   -- (<*>) :: State s f -> State s x -> State s (f x)
   sf <*> sx = State $ \s ->
                     let (f, s1) = (runState sf) s
                         (x, s2) = (runState sx) s1
                     in (f x, s2)
(d) State s is a monad. Give a suitable Monad instance for State s.\text{(d) \texttt{State s} is a monad. Give a suitable Monad instance for \texttt{State s}.}
  haskell  
instance Monad (State s) where
   -- (>>=) :: (State s a) -> (a  -> State s b) -> (State s b)
   sa >>= f = State $ \s -> let (x, s1) = runState sa s
                            in runState (f x) s1
(d) Each of the following expressions is polymorphic. For each expression,give two distinct monomorphic typings. All functions used are listedin the Appendix.\text{(d) Each of the following expressions is polymorphic. For each expression,} \newline \text{give two distinct monomorphic typings. All functions used are listed} \newline \text{in the Appendix.}
  haskell  
-- (i) 
5 :: Int
5 :: Integer

-- (ii)
(\x y z -> y) :: () -> () -> () -> ()
(\x y z -> y) :: () -> Int -> () -> Int

-- (iii)
(minimum $ pure $ pure False) :: [Bool]
(minimum $ pure $ pure False) :: Maybe Bool

--- (iv)
null :: [Int] -> Bool
null :: [Double] -> Bool
Question 6
 This question is about writing complete functional programs\textbf{ This question is about writing complete functional programs}
(c) Write a Haskell program which solves the classic FizzBuzzprogramming problem.\text{(c) Write a Haskell program which solves the classic \texttt{FizzBuzz}} \newline \text{programming problem.}
  haskell  
module Main where

main :: IO ()
main = putStrLn . unlines $ map solve [1..]

solve :: Int -> String
solve n = if s == "" then show n else s where s = fizz n ++ buzz n

fizz, buzz :: Int -> String
fizz n = if n `mod` 3 == 0 then "Fizz" else ""
buzz n = if n `mod` 5 == 0 then "Buzz" else ""
(d) Define intercept :: (String -> String) -> IO () -> IO (),which takes a function f and an IO action a and uses takeOutputto apply the function f to each line of text generated by action,printing the modified version to the terminal’s standard output.\text{(d) Define \texttt{intercept :: (String -> String) -> IO () -> IO ()},} \newline \text{which takes a function \texttt{f} and an IO action a and uses \texttt{takeOutput}} \newline \text{to apply the function \texttt{f} to each line of text generated by action,} \newline \text{printing the modified version to the terminal’s standard output.}
  haskell  
intercept :: (String -> String) -> IO () -> IO ()
intercept f c = takeOutput c >>=  mapM_ (putStrLn . f) . lines


Namespace Logo Namespace0.3L
More from fermicide