Assignment 2: functional patterns #

Exercise 1: utility functions #

Implement the functions below by completing the function stubs in the file Src/Utility.hs.

Hint. Some of these functions can be used to implement others.

Hint. Feel free to create additional (auxiliary) functions to simplify your implementation.

lastMatch #

Implement the function

lastMatch :: (a -> Bool) -> [a] -> Maybe a

such that lastMatch f xs is:

• Just x if x is the last element of the list xs for which f x is True, or
• Nothing if there is no such x.

For instance,

lastMatch even [2,3,4,2,5]

should evaluate to Just 2, whereas

lastMatch even [3,5]

should evaluate to Nothing.

compose #

Terminology. If

$\qquad F = f_1, f_2, \ldots, f_n$

is a list of functions with $f_i \colon X \to X$ for each $f_i$, then we call inductive composition of $F$ the function

$\qquad f_1 \circ f_2 \circ \ldots \circ f_n$

Note. Function composition is associative, so no parenthesis is needed here.

Implement the function

compose :: [a -> a] -> a -> a

such that compose fs is:

• the inductive composition of all functions in fs if fs is nonempty, or
• the identity function otherwise.

For instance,

compose [(* 3), (+ 2)]

is the function \x -> (x + 2) * 3,

compose [(+ 2)]

is the function (+2), and

compose []

is the identity function id.

Hint. You may take advantage of one of the native higher-order functions that we have encountered.

firstAgreement #

Implement the function

firstAgreement :: (Eq b) => (a -> b) -> (a -> b) -> [a] -> Maybe b

such that

firstAgreement f g xs is:

• Just (f x) if x is the first element of the list xs for which f x is equal to g x, or
• Nothing if there is no such x .

For instance,

firstAgreement (`mod` 2) (`mod` 3) [3,7,6]

should evaluate to Just 1, because:

• 7 is the first element x in the list [3,7,6] such that x `mod` 2 == x `mod` 3 and
• 7 `mod` 2 is 1.

Instead,

firstAgreement (`mod` 2) (`mod` 3)[3,8]

should evaluate to Nothing.

keepLastOccIn #

Implement the function

keepLastOccIn :: (Eq a) => a -> [a] -> [a]

such that keepLastOccIn x xs is the list identical to xs for all elements different from x, and where only the last occurrence of x (if any) is retained.

For instance,

keepLastOccIn  2 [1,2,3,2,4,5,2,4]

should evaluate to [1,3,4,5,2,4], whereas

keepLastOccIn  2 [1,3,4]

should evaluate to [1,3,4].

Hint. You may use recursion here, with either:

• additional intermediate results, or
• an accumulator.

discardDups #

Implement the function

discardDups :: (Eq a) => [a] -> [a]

such that discardDups xs is the list identical to xs, but where only the last occurrence of each element of xs is retained.

For instance,

discardDups [1,2,3,2,4,5,2,4]

should evaluate to [1,3,5,2,4].

Exercise 2: tracing a virus #

Data format. We use the following product types to represent infection tests for a virus, as well as meetings:

data Person = PersonC {
    name :: String,
    city :: String
} deriving (Show, Eq)

data Test = TestC {
    subject :: Person,
    testTime :: Int,
    positive :: Bool
} deriving (Show, Eq)

data Meeting = MeetingC {
    meetingTime :: Int,
    attendees :: [Person]
} deriving (Show, Eq)

The value of a testTime or meetingTime attribute is an integer that identifies a day, numbered from a certain origin.

We assume for simplicity that all people have different names.

Running example. We will use the following sample data to illustrate and test the functions that we want to implement:

alice, bob, carol, dan, eve :: Person
alice = PersonC {name = "Alice", city = "Bolzano"}
bob = PersonC {name = "Bob", city = "Bolzano"}
carol = PersonC {name = "Carol", city = "Trento"}
dan = PersonC {name = "Dan", city = "Bolzano"}
eve = PersonC {name = "Eve", city = "Rovereto"}

t1, t2, t3, t4, t5 :: Test
t1 = TestC {subject = alice, testTime = 48, positive = False}
t2 = TestC {subject = alice, testTime = 50, positive = True}
t3 = TestC {subject = alice, testTime = 56, positive = True}
t4 = TestC {subject = bob, testTime = 63, positive = True}
t5 = TestC {subject = carol, testTime = 66, positive = True}

m1, m2, m3, m4 :: Meeting
m1 = MeetingC {meetingTime = 46, attendees = [alice, bob]}
m2 = MeetingC {meetingTime = 54, attendees = [alice, carol, dan, eve]}
m3 = MeetingC {meetingTime = 58, attendees = [bob, carol, dan]}
m4 = MeetingC {meetingTime = 61, attendees = [carol, dan]}

Implement the functions below by completing the function stubs in the file Src/Virus.hs.

Hint. Some of these functions can be used to implement others.

Functions of the previous exercise can be used as well.

Hint. Feel free to create additional (auxiliary) functions to simplify your implementation.

attendances #

Implement the function

attendances :: Person -> [Meeting] -> [Int]

such that attendances p ms contains the times of all meetings in ms that p attended, in the same order as they appear in ms.
For instance,

attendances bob [m1,m2,m3]

should evaluate to [46,58].

neighborsOf #

Implement the function

neighborsOf :: Person -> [Person] -> [String]

such that neighborsOf p ps is the list of names of people in ps who live in the same city as p, excluding p, and in the same order as they appear in ps.
For instance,

neighborsOf alice [alice,bob,carol,dan]

should evaluate to ["Bob", "Dan"].

Restriction. You can assume that the list ps does not contain duplicates (but it may contain p).

firstPositiveTest #

Implement the function

firstPositiveTest :: Person -> [Test] -> Maybe Int

such that firstPositiveTest p ts is:

• Just t if t is the time of the first positive test in ts whose test subject was p, or
• Nothing if there is no such test.

For instance

firstPositiveTest alice [t1,t2,t3]

should evaluate to Just 50, whereas

firstPositiveTest bob [t1,t2,t3]

should evaluate to Nothing.

Restriction. You can assume that tests in ts are in chronological order.

metDuring #

Implement the function

metDuring :: Person -> Person -> Meeting -> Bool

such that metDuring p1 p2 m is True iff p1 and p2 are different people and both attended meeting m.
For instance,

metDuring alice bob m1

should evaluate to True, whereas

metDuring alice bob m2

should evaluate to False.

lastMeetingBefore #

Implement the function

lastMeetingBefore :: Person -> Person -> Int -> [Meeting] -> Maybe Int

such that lastMeetingBefore p1 p2 t ms is:

• Just t' if p1 and p2 are different people and t' is the time of the last meeting that took place earlier than t and where p1 and p2 met, or
• Nothing is there is no such meeting.

Restriction. You can assume that the meetings in ms are sorted in chronological order.

For instance

lastMeetingBefore carol dan 56 [m1,m2,m3]

should evaluate to Just 54, whereas

lastMeetingBefore carol dan 52 [m1,m2,m3]

should evaluate to Nothing.

Hint. You may take advantage of the function metDuring described above.

contactsSince #

Implement the function

contactsSince :: Person -> Int -> [Meeting] -> [String]

such that contactsSince p t ms is the list of names of people that p met in any meeting in ms that took place at a time > t.

Names in the output list can be in any order. This list:

• should not contain duplicates, and
• should not contain the name of p.

For instance

contactsSince carol 56 [m1,m2,m3,m4]

should evaluate to ["Bob","Dan"] or ["Dan", "Bob"].

Hints. You may take advantage of:

• the function discardDups implemented above, and
• the “bind” function >>= for the type “List” (or equivalently, the function concatMap)