FP 2024 Past Paper

Question 1: Data Types and Abstraction in Haskell

Part (a) [3 marks]

Question

Write a Haskell function singular :: [Char] -> [Char] which takes a single string parameter. The result of singular should be an identical string to the input parameter, unless the input string ends in character ‘s’ in which case the result is the same as the input parameter with the final ‘s’ character removed.

For example singular "exams" evaluates to "exam" and singular "foo" evaluates to "foo".

Answer

singular [] = []                  -- 1 mark
singular ['s'] = []               -- 1 mark
singular (x:xs) = x:singular(xs)  -- 1 mark

Accept other solutions involving if expressions, etc. Or clever Data.List calls. If solutions are less efficient then max 2 marks.

Part (b) [2 marks]

Write an appropriate QuickCheck property specification for the singular function.

Answer

-- 1 mark for a sensible check,
-- involving a test for 's'
-- 1 mark for checking empty list
let p = \x -> length x == 0 ||
      if x !!(length x - 1) == 's'
      then x == (singular x) ++ "s"
      else x == (singular x)

Part (c) [7 marks]

Now consider a list of data having the form:

["3", "kings", "5", "little ducks", "2", "green bottles"]

where there are an even number of elements in the list. Elements at even-numbered indexes in the list (i.e. index 0, 2, and 4) are integer values represented as strings. Elements at odd-numbered indexes in the list (i.e. index 1, 3, and 5) are arbitrary strings.

A list with this structure could be processed to generate the following output to the standard output stream:

king king king
little duck little duck little duck little duck little duck
green bottle green bottle

i.e. the integer value represents the number of times the next string in the list is repeatedly printed, although the plural form of the string is turned into a singular by removing the ‘s’ suffix.

Define a Haskell function outputThings :: [String] -> IO() that performs the IO behaviour specified above, given an input parameter with the appropriate elements.

You should make use of the predefined function read :: String -> Int to parse integer values. Do not include any special error checking or handling code—for this part of your answer you can assume valid input values.

My Solution:

outputThings :: [String] -> IO()
outputThings [] = return ()
outputThings (x:y:rest) = do
	let num = (read x) :: Int
	putStrLn (unwords $ replicate num (singular y) )
	outputThings rest

Answer

outputThings :: [String] -> IO()
outputThings [] = return ()                      -- 1 mark
outputThings (num:thing:rest) = do              -- 1 mark
  let n = (read num) :: Int                     -- 1 mark
  let things = take n $ repeat (singular thing) -- 2 marks
  putStrLn $ unwords things                     -- 1 mark
  outputThings rest                             -- 1 mark

Part (d) [5 marks]

Discuss what kind of errors might be manifested by the outputThings function if the input is malformed. How do these errors manifest themselves? Can you suggest a better way to handle such errors? Haskell source code is not required for this answer, although you may provide fragments to illustrate particular points.

Answer

• Pattern match exception if there is not an even number of strings in the list (1 mark)
• Read parse exception if a string that is not a parsable integer appears in the list in an even-indexed element (1 mark)
• Errors manifested as runtime exceptions, causing code to die unexpectedly, terminating program (1 mark)
• 2 marks for sketching out a plausible solution to this problem, either using try or catch with an appropriate handler to skip over invalid elements, or changing the type signature to accommodate a monadic error value such as Maybe or Either with appropriate wrapping.

outputThings (x:y:rest) = do
	result <- try (evaluate (read x :: Int)) :: IO (Either SomeException Int) 
	case result of 
		Right num -> putStrLn (unwords $ replicate num (singular y)) 
		Left _ -> putStrLn $ "Error parsing: " ++ x outputThings rest

Part (e) [3 marks]

Critically appraise whether a list of strings is an appropriate data type to represent this kind of structured data, in general. Either justify the design decision, or briefly suggest an alternative data type to represent the same sort of input.

Answer

The flat string list is a poor representation. A list of (Int,String) pairs might be better, encoding the expected structure more explicitly, or some kind of product data type. This avoids the need to parse Ints from Strings, and avoids the issue with possibly incorrect numbers of elements in the list.

(1 mark for each sensible point, up to a max of 3 marks.)

Question 2: Lambda Calculus in Haskell

Part (a) [3 marks]

Question

The Haskell library function iterate :: (a -> a) -> a -> [a] is used to build up a list of repeated applications of a function. For instance, iterate f x returns the list [x, f x, f (f x), ...]

Write a definition for the iterate function in Haskell.

Answer

iterate :: (a->a) -> a -> [a]
iterate f x = x : (iterate f (f x))

1 mark for cons, 1 for recursive call and 1 for appropriate values in appropriate places. (Accept other sensible solutions.)

Part (b) [2 marks]

Which feature of Haskell enables us to work with functions like iterate that generate infinite data structures. What does this mean in practice?

Answer

• 1 mark for laziness
• 1 mark for explaining that we always operate on finite data in reality, due to finite memory — perhaps using functions like take
• Alternatively, give 1 mark for other sensible point(s)

Part (c) [2 marks]

Question

Recall the concept of Church Numerals from the course. The Church numeral for positive integer n is represented by n applications of a function f to a zero element z. For instance, the second Church numeral is represented by the Haskell expression:

let two f z = f ( f z )

What is the Haskell type of such a Church numeral?

Answer

two :: (a->a) -> a -> a  -- 2 marks

Part (d) [2 marks]

Show, with the use of Haskell source code, how the Church numeral for non-negative integer n can be defined using the iterate function.

Answer

church f z n = (iterate f z) !! n  -- 1 mark

The nth element of the list is the nth numeral (1 mark)

Part (e) [3 marks]

Define the unchurch function in Haskell, which takes a Church numeral and returns the equivalent integer value.

Answer

unchurch :: (a->a) -> a -> a -> Int  -- 1 mark
unchurch numeral = numeral (+1) 0    -- 2 marks

Part (f) [6 marks]

The subtraction operation is difficult in Church numeral representation. What is the nature of the difficulty? Demonstrate with Haskell source code how subtraction might be performed by using the iterate function.

Answer

The problem is that subtraction requires un-applying functions, or doing functional inverses (1 mark). Not all functions f have inverses (1 mark). Basically, we convert both numbers into Ints (1 mark), do the subtraction (1 mark) and then lookup the new value in the iterate infinite list (1 mark).

-- problem is we need to know what f and z are...
sub a b = iterate f z (unchurch a - unchurch b)  -- 1 mark

Part (g) [2 marks]

Discuss whether Church numerals are an appropriate representation for integer arithmetic. What is the key underlying motivation for this representation?

Answer

In general, Church numerals are an abstract, theoretic notation that are not efficient for computation (1 mark). Instead, the encoding is useful to demonstrate the computational power of lambda calculus as a universal computing system (1 mark).

Question 3: Functional Abstractions

Question

Recall that a monoid is defined as a structure that has an identity element and an associative append operation. In Haskell, a monoid must belong to the Semigroup class (which provides the append operation <>) and the Monoid class (which provides the identity element):

class Semigroup m where
    (<>) :: m -> m -> m
 
class (Semigroup m) => Monoid m where
    mempty :: m

Part (a) [3 marks]

Define the function mconcat :: Monoid a => [a] -> a using mempty, <> and either foldl or foldr.

Answer

With foldr:

mconcat :: Monoid m => [m] -> m
mconcat = foldr (\x acc -> x <> acc) mempty

With foldl:

mconcat :: Monoid m => [m] -> m
mconcat = foldl (\acc x -> acc <> x) mempty

1 mark for attempt to use a fold; 1 mark for attempt to use concatenation; 1 mark for complete solution.

Part (b)

Question

HTML is a hierarchical document markup language used for defining web pages. Consider the following HTML document:

<html\>
<h1>Welcome to COMPSCI4021 Functional Programming</h1>
<a href="/coursework">Coursework</a>
</html>

Here, html, h1, and a are tags that indicate some element on a web page: each tag may have a list of attributes (e.g., href=“/coursework” portion of the a tag, where href is a key and /coursework is the value), and children elements. HTML also supports text (e.g., Welcome to COMPSCI4021 Functional Programming and Coursework).

We can define a monoidal HTML data type as follows:

type Attribute = (String, String)
data HTML = HTMLSiblings [HTML]
          | HTMLText String
          | HTMLTag String [Attribute] HTML
 
instance Semigroup HTML where
    (HTMLSiblings []) <> x = x
    x <> (HTMLSiblings []) = x
    (HTMLSiblings xs1) <> (HTMLSiblings xs2) =
        HTMLSiblings (xs1 ++ xs2)
    (HTMLSiblings xs) <> x = HTMLSiblings (xs ++ [x])
    x <> (HTMLSiblings xs) = HTMLSiblings (x : xs)
    x <> y = HTMLSiblings [x, y]
 
instance Monoid HTML where
    mempty = HTMLSiblings []

Here, HTMLSiblings [HTML] defines a list of HTML elements on the same level; HTMLText String defines an HTML text element containing the given text; and HTMLTag String [Attribute] HTML defines an HTML element with the given tag name, attributes, and child. We can define our earlier example using the HTML data type as follows:

HTMLTag "html" []
(HTMLSiblings [
    HTMLTag "h1" []
    (HTMLText "Welcome to COMPSCI4021 Functional Programming"),
    HTMLTag "a" [("href", "/coursework")] (HTMLText "Coursework")
]
)

Part (b)(i) [3 marks]

Write the following HTML tree using the HTML data type and the (<>) and mempty functions.

\<html>
<h1>Welcome to the University of Glasgow</h1>
<img src="/uofg-logo.png"></img>
\<div id="search-label" style="font-weight: bold">
Search
</div>
\<input type="text"></input>
</html>

Answer

htmlExample :: HTML
htmlExample =
    HTMLTag "html" []
    ((HTMLTag "h1" []
    (HTMLText "Welcome to the University of Glasgow")) <>
    (HTMLTag "img" [("src", "/uofg-logo.png")] mempty) <>
    (HTMLTag "div" [("id", "search-label"),
                    ("style", "font-weight: bold")]
    (HTMLText "Search")) <>
    (HTMLTag "input" [("type", "text")] mempty))

1 mark for attempt to use HTMLTag, 1 mark for correctly using <> and mempty (or HTMLAppend and HTMLSiblings []), final mark for complete solution.

Part (b)(ii) [3 marks]

Question

Write a function stripAttrs :: HTML → HTML that removes all attributes in a tree. For example:

stripAttrs (HTMLTag "html" []
          (HTMLTag "a" [("href", "google.com")] (HTMLText "Google")))
= HTMLTag "html" [] (HTMLTag "a" [] (HTMLText "Google"))

Answer

stripAttrs :: HTML -> HTML
stripAttrs (HTMLSiblings xs) =
    HTMLSiblings (map stripAttrs xs)
stripAttrs (HTMLText txt) = (HTMLText txt)
stripAttrs (HTMLTag tag _ html) =
    HTMLTag tag [] (stripAttrs html)

1 mark for case split; 1 mark for a sensible recursive call; 1 mark for completely correct solution.

Part (b)(iii) [5 marks]

Write a Show instance for HTML. Your instance should correctly indent child elements and each sibling element should be on a new line. You may write helper functions.

Answer

instance Show HTML where
    show = showHelper 0
    where
      showHelper :: Int -> HTML -> String
      showHelper level (HTMLSiblings xs) =
          unlines $ map (showHelper level) xs
      showHelper level (HTMLText txt) = indent level ++ txt
      showHelper level (HTMLTag tag attrs child) =
          indent level ++
          "<" ++ tag ++ (showAttrs attrs) ++ ">" ++ "\n" ++
          (showHelper (level + 1) child) ++ "\n" ++
          indent level ++ "</" ++ tag ++ ">"
      
      showAttr :: Attribute -> String
      showAttr (k, v) = k ++ "=\"" ++ v ++ "\""
      
      showAttrs :: [Attribute] -> String
      showAttrs [] = ""
      showAttrs ats = " " ++ (unwords $ map showAttr ats)
      
      indent :: Int -> String
      indent n = replicate (n * 2) ' '

1 mark for defining helper function taking a level as a parameter; 1 mark for case split; 1 mark for sensible recursive calls; 1 mark for putting each sibling on a correctly-indented new line; 1 mark for complete solution.

Part (b)(iv) [1 mark]

The definition of (<>) includes the following two clauses:

• (HTMLSiblings []) <> x = x
• x <> (HTMLSiblings []) = x

Why are these necessary?

Answer

These two equations are required to make sure the instance satisfies the identity monoid laws. Without these, we would have:

(HTMLSiblings []) <> (HTMLText "Hello") =
    HTMLSiblings [HTMLText "Hello"]

Which doesn’t match (HTMLText “Hello”)

Part (c)

The HTML data type and Monoid instance could alternatively be defined as follows:

data HTML2 = HTML2Empty
           | HTML2Append HTML2 HTML2
           | HTML2Text String
           | HTML2Tag String [Attribute] HTML2
 
instance Monoid HTML2 where
    mempty = HTML2Empty
 
instance Semigroup HTML2 where
    HTML2Empty <> m = m
    m <> HTML2Empty = m
    m1 <> m2 = HTML2Append m1 m2

Part (c)(i) [2 marks]

Why does this definition violate the monoid laws? Give a counterexample.

Answer

The definition violates the associativity law:

HTMLText "Hello" <> (HTMLText "FP" <> HTMLText "Students")
=
HTMLAppend (HTMLText "Hello")
   (HTMLAppend (HTMLText "FP") (HTMLText "Students")
 
but
 
(HTMLText "Hello" <> HTMLText "FP") <> HTMLText "Students")
=
HTMLAppend
   (HTMLAppend (HTMLText "Hello") (HTMLText "FP"))
   (HTMLText "Students")

1 mark for stating that it violates the associativity law; 1 mark for counterexample.

Part (c)(ii) [3 marks]

How could you modify the definition of (<>) to ensure that it satisfies the monoid laws, without changing the HTML2 type?

Answer

It would be necessary to either left- or right-bias the append operation:

instance Semigroup HTML2 where
    HTML2Empty <> m = m
    m <> HTML2Empty = m
    (HTML2Append m1 m2) <> m3 =
        HTML2Append m1 (HTML2Append m2 m3)
    m1 <> m2 = HTML2Append m1 m2

This solution assumes that any append operations in m1, m2, and m3 are already right-biased.

Alternatively it would be possible to normalise the structure after constructing it:

normalise :: HTML2 -> HTML2
normalise (HTML2Append HTML2Empty m) = m
normalise (HTML2Append m HTML2Empty) = m
normalise (HTML2Append (HTML2Append m1 m2) m3) =
    HTML2Append (normalise m1)
        (HTML2Append (normalise m2) (normalise m3))

1 mark for an attempt to pattern match on HTML2Append, 1 mark for an attempt at reassociating, and 1 mark for the full definition.