微信客服：xiaoxionga100
微信客服：ITCS521
Q1-haskell代写
时间：2023-06-12
Q1 Preamble
0 Points
COMP1100 Final Exam, Semester 2 2022
You must acknowledge the following integrity pledge
before proceeding. Please read carefully and check all
the boxes.
Read and check o the following instructions:
1. This examination is timed and will be three and a half
hours long (210 minutes).
I am committed to being a person of integrity.
I pledge, as a member of the ANU community, to
abide by and uphold the standards of academic
integrity outlined in the ANU statement on
honesty and plagiarism, I am aware of the
relevant legislation, and understand the
consequences of breaching those rules.
I will not communicate in any way with anyone
else during this exam. This includes asking
questions in any online forum.
I acknowledge that this exam is protected by
copyright and that copying or sharing any of its
content will violate that copyright.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
1 of 25 7/3/23, 14:33
2. Permitted materials. This is an open book exam. You
might in particular nd the
course website, and the [Prelude documentation]
useful.
4. Marks, exam weighting and hurdle:
5. Redeemable Mid-Semester
6. Marking variation between gradescope and nal
grade.
Your marks may vary between what you see on
gradescope and the nal grade you receive in wattle.
This can happen in your favour, for example: Your code
does not compile due to a small syntax error. You
receive no marks in gradescope, but partial marks in
wattle.
This can also happen against your favour, for example:
You write code that passes the tests in gradescope, but
does not actually solve the underlying problem. You
receive full marks in gradescope, but partial marks in
wattle.
Note the remaining time at the top right of this
screen. Set an alarm for yourself if you need one.
You may use any materials you wish but all work
must be your own.
This exam is worth 100 marks and 50% of your
nal grade.
A minimum score of 40 marks (20% of your nal
grade) is required to pass this course.
This exam is redeemable against your mid-
semester exam mark. If the nal exam result
scaled to 10% is higher than your mid-semester
exam, your mid-semester mark will be replaced
by this scaled mark.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
2 of 25 7/3/23, 14:33
Finally, here are some tips:
Q2 Sets and Functions 1 - Sums
1 Point
Given two arbitrary sets of integers A and B which of
the following represents a possible element of their
sum?
Q3 Sets and Functions 2 - Products
1 Point
Given two arbitrary sets of integers A and B which of
the following represents a possible element of their
product?
I acknowledge that the mark I receive in
gradescope may not reect the mark I receive in
wattle for this nal exam.
Focus on the multiple choice and 5-mark
programming questions rst, these are worth
65% of the total exam marks.
Attempt everything, we can give part marks for
partial work, but we can't give any marks for
blanks submissions or no response.
(2, 3)
2
(2, left)
{2, 3}
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
3 of 25 7/3/23, 14:33
Q4 Sets and Functions 3 - Functions
1 Point
given:
what is the result of:
Q5 Operations and Data Types - Common Operations
1 Point
Which of the following Haskell functions is a valid test
for an odd Integer value.
Solution A
f :: Integer -> Bool
f x = mod x 2 == 1
Solution B
f :: Integer -> Bool
f x = x `mod` 2 == 0
Solution C
(2, 3)
2
(2, left)
{2, 3}
f(x) = x− 1
g(x) = x× 2
(f ∘ g)(2)
1
2
3
4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
4 of 25 7/3/23, 14:33
f :: Integer -> Bool
f x = div x 2 == 0
Solution D
f :: Integer -> Bool
f x = div x 2 == 1
Select the correct solution below:
Q6 Operations and Data Types - Data Types
1 Point
What is the name of the in the
following data type declaration?
data a b = MkFoo a b
Q7 Operations and Data Types - Data Types
1 Point
What is the name of the in the
following data type declaration?
data Foo a b = a b
A
B
C
D
highlighted syntax
Foo
Type Name
Data Type
Type Constructor
Data Constructor
highlighted syntax
MkFoo
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
5 of 25 7/3/23, 14:33
Q8 Recursive Data Types and Polymorphism - Lists
1 Point
Which of the following types represents a custom or
user-dened list data type?
Q9 Recursive Data Types and Polymorphism - Lists
1 Point
In the standard denition of a list which
of the denition is required for
the type to be a recursive data type?
(i.e what part of the denition is the recursive part?)
Q10 Recursive Data Types and Polymorphism -
Polymorphism
1 Point
Which of these is a valid polymorphic type?
Type Name
Data Type
Type Constructor
Data Constructor
data List = Nil | Cons () List
data MyList a = Null | Node (MyList a) a (MyList a)
data [a] = [] | a : [a]
data List a = Nil | Cons a (List a)
highlighted syntax
data = a : [a][a]
data [a] = a : [a]
data [a] = a : [a]
data [a] = : [a]a
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
6 of 25 7/3/23, 14:33
Q11 Lists, Local Denitions, and Code Quality - Code
Quality
1 Point
Fill in the blank:
"___ involves writing tests without looking at your
code."
Q12 Lists, Local Denitions, and Code Quality - Local
Denitions
1 Point
When is it appropriate to use local denitions?
Q13 Lists, Local Denitions, and Code Quality - Lists
1 Point
Given the following examples of an unknown function
f :
data A Int String = B (Int -> String)
data A int string = B (int -> string)
data A = B (int -> string)
data A = B (Int -> String)
Black box testing
White box testing
Appropriate testing procedure
Best testing practice
When we want to reuse a function more than once.
When we want to want to rename pieces of our code.
When we want to simplify our calculations, or write
a helper function that is only used in our top-level
function denition.
When we want to accumulate an intermediate
computation.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
7 of 25 7/3/23, 14:33
f [1, 2, 3] ['a', 'b', 'c'] = [(1, 'a'), (2, 'b'), (3, 'c')]
f [(+), (*)] [(1, 2), (3, 4)] = [((+), (1, 2)), ((*), (3, 4))]
f [] [True, False, True] = []
f [] [] = []
What common Haskell function in the prelude behaves
the same as f for the above inputs?
Q14 Polymorphism - Functions
1 Point
Fill in the blank.
"A function f :: bool -> bool is an example of a ___
function?"
Q15 Polymorphism - Functions 2
1 Point
Fill in the blank.
"A function f :: Bool -> Bool is an example of a ___
function?"
tail
merge
join
zip
polymorphic
hylomorphic
monomorphic
catamorphic
polymorphic
hylomorphic
monomorphic
catamorphic
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
8 of 25 7/3/23, 14:33
Q16 Polymorphism - Functions 3
1 Point
Fill in the blank.
"A function f :: Show a => a -> a is an example of a(n)
___ function?"
Q17 Higher Order Functions 1
1 Point
What is the name of the syntax used in the denition of
the following Haskell?
f :: a -> a -> (a, a)
f = \x -> \y -> (x, y)
Q18 Higher Order Functions 2
1 Point
Which of the following denitions results in g being a
higher order function?
incorrect (this is not a valid Haskell type signature)
ad-hoc polymorphic
ad-hoc catamorphic
parametrically polymorphic
A smart constructor for pairs
A polymorphic pair function
A data constructor
A lambda expression, or anonymous function
g = map f xs
g = map f
g = map
none of the above.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
9 of 25 7/3/23, 14:33
Q19 Type Classes
1 Point
Given a datatype:
data Foo a = Bar a | Baz a | Qux a
Which of the following solutions denes a valid and
complete Ord instance?
Solution 1.
instance Ord Foo where
Bar x <= Baz y = True
Baz x <= Quz y <= True
Bar x <= Bar x <= True
Baz x <= Baz x <= True
Quz x <= Qux x <= True
_ <= _ = False
Solution 2.
instance Ord a => Ord (Foo a) where
(Bar x) > (Bar y) = x > y
(Baz x) > (Baz y) = x > y
(Qux x) > (Qux y) = x > y
(Qux _) > (Baz _) = True
(Qux _) > (Bar _) = True
(Baz _) > (Bar _) = True
_ > _ = False
Solution 3.
instance Ord a => Ord (Foo a) where
max (Qux x) (Qux y) = max x y
max _ (Qux x) = Qux x
min (Bar x) (Bar y) = min x y
min (Bar x) _ = Bar x
Solution 4.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
10 of 25 7/3/23, 14:33
instance Ord a => Ord (Foo a) where
compare (Bar x) (Bar y) = compare x y
compare (Baz x) (Baz y) = compare x y
compare (Qux x) (Qux y) = compare x y
compare (Bar _) (Baz _) = LT
compare (Bar _) (Qux _) = LT
compare (Baz _) (Qux _) = LT
compare _ _ = GT
Select the correct solution below:
Q20 Binary Tree
1 Point
Assume the common denition of the binary tree data
type used in this course.
Which of the following is a function to calculate tree
height?
(where the height of the root node is always 0).
Solution 1.
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = max (1 + f l) (f r)
Solution 2.
f :: BTree a -> Integer
f Null = 0
f (Node l x r)
| f l <= f r = 1 + 0 * (f l) + 1 * (f l)
| otherwise = 1 + 1 * (f l) + 0 * (f r)
Solution 3.
Solution 1
Solution 2
Solution 3
Solution 4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
11 of 25 7/3/23, 14:33
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = 1 + f l + f r
Solution 4.
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = 1 + max (f l) (f r)
Select the correct solution below:
Q21 Binary Search Tree
1 Point
Which of the following represents a function to nd an
element in a balanced binary search tree in
complexity, where is the number of nodes in the tree?
Solution 1.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| x == value = Just x
| otherwise = op (nd l value) (nd r value)
where
op :: Ord a => Maybe a -> Maybe a -> Maybe a
op Nothing Nothing = Nothing
op Nothing y = y
op x Nothing = x
op x y
| x > y = x
| otherwise = y
Solution 1
Solution 2
Solution 3
Solution 4
O(log(n))
n
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
12 of 25 7/3/23, 14:33
Solution 2.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| value == x = Just x
| value < x = nd l value
| otherwise = nd r value
Solution 3.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| x == value
|| nd l value == Just value
|| nd r value == Just value = Just value
| otherwise = Nothing
Solution 4.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value = Just x
Choose the correct solution below:
Q22 Rose Tree
1 Point
Which of the following denitions best describes a rose
tree?
Solution 1
Solution 2
Solution 3
Solution 4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
13 of 25 7/3/23, 14:33
Q23 Tree Traversal
1 Point
Given the following depiction of a tree of type
BTree Char:
'l'
/ \
'e' 'o'
/ \
'h' 'l'
Which of the following solutions results in the value
"hello" of type String, when applied to the example
above?
Solution A
f :: BTree a -> [a]
f Null = []
f (Node l x r) = [x] ++ f l ++ f r
Solution B
f :: BTree a -> [a]
f Null = []
f (Node l x r) = f l ++ f r ++ [x]
Solution C
A tree where each node may have zero or more
children.
A n-ary branching tree for some n.
A recursive data structure with a Null case and a
Node case.
A tree with a non-empty list of trees inside each
node.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
14 of 25 7/3/23, 14:33
f :: BTree a -> [a]
f Null = []
f (Node l x r) = f l ++ [x] ++ f r
Choose your answer below:
Q24 Trees
1 Point
What is the most-general type of tree represented by
the following diagram?
o
/ | \
o o o
/ \ / \
o o o o
Q25 Branching Factor
1 Point
Given the denition of a Rose tree:
data Rose a = MkRose a [Rose a]
Solution A
Solution B
Solution C
None of the above, these functions do not return
type String.
A rose tree.
A binary tree.
A game tree.
A binary search tree.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
15 of 25 7/3/23, 14:33
and an example tree 't':
t :: Rose ()
t = MkRose ()
[MkRose ()
[MkRose () [],
MkRose ()
[MkRose () [],
MkRose () []],
MkRose ()
[MkRose () []]]]
What is the largest branching factor, of t?
Q26 Non-Termination
1 Point
Given an innite list (or stream) of data:
double :: [Int]
double = 1 : zipWith (+) double double
and any predicate of type p :: Int -> Bool , which of the
following functions terminate?
Q27 Complexity
1 Point
4
3
2
1
foldr (&&) True (map p double)
foldr (&&) True (map p double) || True
False && foldr (&&) True (map p double)
True && foldr (&&) True (map p double)
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
16 of 25 7/3/23, 14:33
For each running time function below, select those that
are linear ( ):
Q28 Sort
1 Point
Consider the sorting algorithm which repeatedly
inserts the elements of a list into an initially empty
binary search tree. The insertion function used is
insert1 :: Ord a => a -> BTree a -> BTree a
insert1 x Null = Node Null x Null
insert1 x (Node l y r)
| x <= y = Node (insert1 x l) y r
| otherwise = Node l y (insert1 x r)
which is guaranteed to keep the elements stored in the
tree’s nodes in the correct order. Finally, the tree is
attened, creating a sorted list.
What is this algorithm's worst case complexity?
Q29 Search
1 Point
O(n)
: time-taken(n) = 4n −2 4n+ 1
: time-taken(n) = 3n+ 106
: time-taken(n) = n− 2
: time-taken(n) = n log n
O(log n)
O(n)
O(n logn)
O(n )2
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
17 of 25 7/3/23, 14:33
What do we mean by a 'divide an conquer' algorithm?
Q30 Non-Termination
1 Point
Given the following Haskell code
data ITree a = Node (ITree a) a (ITree a)
deriving Show
instance Functor ITree where
fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)
ipt :: ITree a -> ITree a
ipt (Node l x r) = Node (ipt r) x (ipt l)
atten :: ITree a -> [a]
atten (Node l x r) = [x] ++ atten l ++ atten r
Which of the following Haskell functions will terminate
when given an ITree Integer as an argument?
Q31 Laziness
1 Point
Splitting a problem in half always involves division
by 2.
Splitting a problem in half at each step can make it
simpler to solve.
Splitting a problem in half guarantees
complexity.
O(logN)
Splitting a problem in half creates twice the
problems to solve.
show . (take 10) . atten
show . (fmap (+1))
show . ipt
show .atten
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
18 of 25 7/3/23, 14:33
What do we mean when we say a language is a lazy
language?
Q32 Programming Questions
0 Points
There are 10 programming questions.
• 7 questions worth 5 marks (35 total)
• 3 advanced questions worth 11, 12, and 12 marks
respectively (35 total)
Each question below contains a link to the appropriate
Haskell le, along with some supplementary
information where required.
Download the Haskell le, complete the problem
specied within, and upload it according to the
submission link for each problem.
The submission links are also on your gradescope
dashboard with the appropriate question number and
le name.
Q32.1 Greet.hs
0 Points
(Contrary to the statement above, this question is
worth 5 marks!)
1. Download Greet.hs from here.
2. Complete the problem inside the Haskell le.
3. Submit your working Haskell le here.
Haskell is only used by the laziest of programmers.
Expressions are always evaluated.
Haskell can have non-terminating terms, such as
innite lists.
Expressions are evaluated only when they are used.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
19 of 25 7/3/23, 14:33
0 Points
COMP1100 Final Exam, Semester 2 2022
You must acknowledge the following integrity pledge
before proceeding. Please read carefully and check all
the boxes.
Read and check o the following instructions:
1. This examination is timed and will be three and a half
hours long (210 minutes).
I am committed to being a person of integrity.
I pledge, as a member of the ANU community, to
abide by and uphold the standards of academic
integrity outlined in the ANU statement on
honesty and plagiarism, I am aware of the
relevant legislation, and understand the
consequences of breaching those rules.
I will not communicate in any way with anyone
else during this exam. This includes asking
questions in any online forum.
I acknowledge that this exam is protected by
copyright and that copying or sharing any of its
content will violate that copyright.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
1 of 25 7/3/23, 14:33
2. Permitted materials. This is an open book exam. You
might in particular nd the
course website, and the [Prelude documentation]
useful.
4. Marks, exam weighting and hurdle:
5. Redeemable Mid-Semester
6. Marking variation between gradescope and nal
grade.
Your marks may vary between what you see on
gradescope and the nal grade you receive in wattle.
This can happen in your favour, for example: Your code
does not compile due to a small syntax error. You
receive no marks in gradescope, but partial marks in
wattle.
This can also happen against your favour, for example:
You write code that passes the tests in gradescope, but
does not actually solve the underlying problem. You
receive full marks in gradescope, but partial marks in
wattle.
Note the remaining time at the top right of this
screen. Set an alarm for yourself if you need one.
You may use any materials you wish but all work
must be your own.
This exam is worth 100 marks and 50% of your
nal grade.
A minimum score of 40 marks (20% of your nal
grade) is required to pass this course.
This exam is redeemable against your mid-
semester exam mark. If the nal exam result
scaled to 10% is higher than your mid-semester
exam, your mid-semester mark will be replaced
by this scaled mark.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
2 of 25 7/3/23, 14:33
Finally, here are some tips:
Q2 Sets and Functions 1 - Sums
1 Point
Given two arbitrary sets of integers A and B which of
the following represents a possible element of their
sum?
Q3 Sets and Functions 2 - Products
1 Point
Given two arbitrary sets of integers A and B which of
the following represents a possible element of their
product?
I acknowledge that the mark I receive in
gradescope may not reect the mark I receive in
wattle for this nal exam.
Focus on the multiple choice and 5-mark
programming questions rst, these are worth
65% of the total exam marks.
Attempt everything, we can give part marks for
partial work, but we can't give any marks for
blanks submissions or no response.
(2, 3)
2
(2, left)
{2, 3}
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
3 of 25 7/3/23, 14:33
Q4 Sets and Functions 3 - Functions
1 Point
given:
what is the result of:
Q5 Operations and Data Types - Common Operations
1 Point
Which of the following Haskell functions is a valid test
for an odd Integer value.
Solution A
f :: Integer -> Bool
f x = mod x 2 == 1
Solution B
f :: Integer -> Bool
f x = x `mod` 2 == 0
Solution C
(2, 3)
2
(2, left)
{2, 3}
f(x) = x− 1
g(x) = x× 2
(f ∘ g)(2)
1
2
3
4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
4 of 25 7/3/23, 14:33
f :: Integer -> Bool
f x = div x 2 == 0
Solution D
f :: Integer -> Bool
f x = div x 2 == 1
Select the correct solution below:
Q6 Operations and Data Types - Data Types
1 Point
What is the name of the in the
following data type declaration?
data a b = MkFoo a b
Q7 Operations and Data Types - Data Types
1 Point
What is the name of the in the
following data type declaration?
data Foo a b = a b
A
B
C
D
highlighted syntax
Foo
Type Name
Data Type
Type Constructor
Data Constructor
highlighted syntax
MkFoo
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
5 of 25 7/3/23, 14:33
Q8 Recursive Data Types and Polymorphism - Lists
1 Point
Which of the following types represents a custom or
user-dened list data type?
Q9 Recursive Data Types and Polymorphism - Lists
1 Point
In the standard denition of a list which
of the denition is required for
the type to be a recursive data type?
(i.e what part of the denition is the recursive part?)
Q10 Recursive Data Types and Polymorphism -
Polymorphism
1 Point
Which of these is a valid polymorphic type?
Type Name
Data Type
Type Constructor
Data Constructor
data List = Nil | Cons () List
data MyList a = Null | Node (MyList a) a (MyList a)
data [a] = [] | a : [a]
data List a = Nil | Cons a (List a)
highlighted syntax
data = a : [a][a]
data [a] = a : [a]
data [a] = a : [a]
data [a] = : [a]a
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
6 of 25 7/3/23, 14:33
Q11 Lists, Local Denitions, and Code Quality - Code
Quality
1 Point
Fill in the blank:
"___ involves writing tests without looking at your
code."
Q12 Lists, Local Denitions, and Code Quality - Local
Denitions
1 Point
When is it appropriate to use local denitions?
Q13 Lists, Local Denitions, and Code Quality - Lists
1 Point
Given the following examples of an unknown function
f :
data A Int String = B (Int -> String)
data A int string = B (int -> string)
data A = B (int -> string)
data A = B (Int -> String)
Black box testing
White box testing
Appropriate testing procedure
Best testing practice
When we want to reuse a function more than once.
When we want to want to rename pieces of our code.
When we want to simplify our calculations, or write
a helper function that is only used in our top-level
function denition.
When we want to accumulate an intermediate
computation.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
7 of 25 7/3/23, 14:33
f [1, 2, 3] ['a', 'b', 'c'] = [(1, 'a'), (2, 'b'), (3, 'c')]
f [(+), (*)] [(1, 2), (3, 4)] = [((+), (1, 2)), ((*), (3, 4))]
f [] [True, False, True] = []
f [] [] = []
What common Haskell function in the prelude behaves
the same as f for the above inputs?
Q14 Polymorphism - Functions
1 Point
Fill in the blank.
"A function f :: bool -> bool is an example of a ___
function?"
Q15 Polymorphism - Functions 2
1 Point
Fill in the blank.
"A function f :: Bool -> Bool is an example of a ___
function?"
tail
merge
join
zip
polymorphic
hylomorphic
monomorphic
catamorphic
polymorphic
hylomorphic
monomorphic
catamorphic
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
8 of 25 7/3/23, 14:33
Q16 Polymorphism - Functions 3
1 Point
Fill in the blank.
"A function f :: Show a => a -> a is an example of a(n)
___ function?"
Q17 Higher Order Functions 1
1 Point
What is the name of the syntax used in the denition of
the following Haskell?
f :: a -> a -> (a, a)
f = \x -> \y -> (x, y)
Q18 Higher Order Functions 2
1 Point
Which of the following denitions results in g being a
higher order function?
incorrect (this is not a valid Haskell type signature)
ad-hoc polymorphic
ad-hoc catamorphic
parametrically polymorphic
A smart constructor for pairs
A polymorphic pair function
A data constructor
A lambda expression, or anonymous function
g = map f xs
g = map f
g = map
none of the above.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
9 of 25 7/3/23, 14:33
Q19 Type Classes
1 Point
Given a datatype:
data Foo a = Bar a | Baz a | Qux a
Which of the following solutions denes a valid and
complete Ord instance?
Solution 1.
instance Ord Foo where
Bar x <= Baz y = True
Baz x <= Quz y <= True
Bar x <= Bar x <= True
Baz x <= Baz x <= True
Quz x <= Qux x <= True
_ <= _ = False
Solution 2.
instance Ord a => Ord (Foo a) where
(Bar x) > (Bar y) = x > y
(Baz x) > (Baz y) = x > y
(Qux x) > (Qux y) = x > y
(Qux _) > (Baz _) = True
(Qux _) > (Bar _) = True
(Baz _) > (Bar _) = True
_ > _ = False
Solution 3.
instance Ord a => Ord (Foo a) where
max (Qux x) (Qux y) = max x y
max _ (Qux x) = Qux x
min (Bar x) (Bar y) = min x y
min (Bar x) _ = Bar x
Solution 4.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
10 of 25 7/3/23, 14:33
instance Ord a => Ord (Foo a) where
compare (Bar x) (Bar y) = compare x y
compare (Baz x) (Baz y) = compare x y
compare (Qux x) (Qux y) = compare x y
compare (Bar _) (Baz _) = LT
compare (Bar _) (Qux _) = LT
compare (Baz _) (Qux _) = LT
compare _ _ = GT
Select the correct solution below:
Q20 Binary Tree
1 Point
Assume the common denition of the binary tree data
type used in this course.
Which of the following is a function to calculate tree
height?
(where the height of the root node is always 0).
Solution 1.
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = max (1 + f l) (f r)
Solution 2.
f :: BTree a -> Integer
f Null = 0
f (Node l x r)
| f l <= f r = 1 + 0 * (f l) + 1 * (f l)
| otherwise = 1 + 1 * (f l) + 0 * (f r)
Solution 3.
Solution 1
Solution 2
Solution 3
Solution 4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
11 of 25 7/3/23, 14:33
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = 1 + f l + f r
Solution 4.
f :: BTree a -> Integer
f Null = 0
f (Node l x r) = 1 + max (f l) (f r)
Select the correct solution below:
Q21 Binary Search Tree
1 Point
Which of the following represents a function to nd an
element in a balanced binary search tree in
complexity, where is the number of nodes in the tree?
Solution 1.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| x == value = Just x
| otherwise = op (nd l value) (nd r value)
where
op :: Ord a => Maybe a -> Maybe a -> Maybe a
op Nothing Nothing = Nothing
op Nothing y = y
op x Nothing = x
op x y
| x > y = x
| otherwise = y
Solution 1
Solution 2
Solution 3
Solution 4
O(log(n))
n
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
12 of 25 7/3/23, 14:33
Solution 2.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| value == x = Just x
| value < x = nd l value
| otherwise = nd r value
Solution 3.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value
| x == value
|| nd l value == Just value
|| nd r value == Just value = Just value
| otherwise = Nothing
Solution 4.
nd :: Ord a => BTree a -> a -> Maybe a
nd Null value = Nothing
nd (Node l x r) value = Just x
Choose the correct solution below:
Q22 Rose Tree
1 Point
Which of the following denitions best describes a rose
tree?
Solution 1
Solution 2
Solution 3
Solution 4
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
13 of 25 7/3/23, 14:33
Q23 Tree Traversal
1 Point
Given the following depiction of a tree of type
BTree Char:
'l'
/ \
'e' 'o'
/ \
'h' 'l'
Which of the following solutions results in the value
"hello" of type String, when applied to the example
above?
Solution A
f :: BTree a -> [a]
f Null = []
f (Node l x r) = [x] ++ f l ++ f r
Solution B
f :: BTree a -> [a]
f Null = []
f (Node l x r) = f l ++ f r ++ [x]
Solution C
A tree where each node may have zero or more
children.
A n-ary branching tree for some n.
A recursive data structure with a Null case and a
Node case.
A tree with a non-empty list of trees inside each
node.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
14 of 25 7/3/23, 14:33
f :: BTree a -> [a]
f Null = []
f (Node l x r) = f l ++ [x] ++ f r
Choose your answer below:
Q24 Trees
1 Point
What is the most-general type of tree represented by
the following diagram?
o
/ | \
o o o
/ \ / \
o o o o
Q25 Branching Factor
1 Point
Given the denition of a Rose tree:
data Rose a = MkRose a [Rose a]
Solution A
Solution B
Solution C
None of the above, these functions do not return
type String.
A rose tree.
A binary tree.
A game tree.
A binary search tree.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
15 of 25 7/3/23, 14:33
and an example tree 't':
t :: Rose ()
t = MkRose ()
[MkRose ()
[MkRose () [],
MkRose ()
[MkRose () [],
MkRose () []],
MkRose ()
[MkRose () []]]]
What is the largest branching factor, of t?
Q26 Non-Termination
1 Point
Given an innite list (or stream) of data:
double :: [Int]
double = 1 : zipWith (+) double double
and any predicate of type p :: Int -> Bool , which of the
following functions terminate?
Q27 Complexity
1 Point
4
3
2
1
foldr (&&) True (map p double)
foldr (&&) True (map p double) || True
False && foldr (&&) True (map p double)
True && foldr (&&) True (map p double)
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
16 of 25 7/3/23, 14:33
For each running time function below, select those that
are linear ( ):
Q28 Sort
1 Point
Consider the sorting algorithm which repeatedly
inserts the elements of a list into an initially empty
binary search tree. The insertion function used is
insert1 :: Ord a => a -> BTree a -> BTree a
insert1 x Null = Node Null x Null
insert1 x (Node l y r)
| x <= y = Node (insert1 x l) y r
| otherwise = Node l y (insert1 x r)
which is guaranteed to keep the elements stored in the
tree’s nodes in the correct order. Finally, the tree is
attened, creating a sorted list.
What is this algorithm's worst case complexity?
Q29 Search
1 Point
O(n)
: time-taken(n) = 4n −2 4n+ 1
: time-taken(n) = 3n+ 106
: time-taken(n) = n− 2
: time-taken(n) = n log n
O(log n)
O(n)
O(n logn)
O(n )2
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
17 of 25 7/3/23, 14:33
What do we mean by a 'divide an conquer' algorithm?
Q30 Non-Termination
1 Point
Given the following Haskell code
data ITree a = Node (ITree a) a (ITree a)
deriving Show
instance Functor ITree where
fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)
ipt :: ITree a -> ITree a
ipt (Node l x r) = Node (ipt r) x (ipt l)
atten :: ITree a -> [a]
atten (Node l x r) = [x] ++ atten l ++ atten r
Which of the following Haskell functions will terminate
when given an ITree Integer as an argument?
Q31 Laziness
1 Point
Splitting a problem in half always involves division
by 2.
Splitting a problem in half at each step can make it
simpler to solve.
Splitting a problem in half guarantees
complexity.
O(logN)
Splitting a problem in half creates twice the
problems to solve.
show . (take 10) . atten
show . (fmap (+1))
show . ipt
show .atten
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
18 of 25 7/3/23, 14:33
What do we mean when we say a language is a lazy
language?
Q32 Programming Questions
0 Points
There are 10 programming questions.
• 7 questions worth 5 marks (35 total)
• 3 advanced questions worth 11, 12, and 12 marks
respectively (35 total)
Each question below contains a link to the appropriate
Haskell le, along with some supplementary
information where required.
Download the Haskell le, complete the problem
specied within, and upload it according to the
submission link for each problem.
The submission links are also on your gradescope
dashboard with the appropriate question number and
le name.
Q32.1 Greet.hs
0 Points
(Contrary to the statement above, this question is
worth 5 marks!)
1. Download Greet.hs from here.
2. Complete the problem inside the Haskell le.
3. Submit your working Haskell le here.
Haskell is only used by the laziest of programmers.
Expressions are always evaluated.
Haskell can have non-terminating terms, such as
innite lists.
Expressions are evaluated only when they are used.
View Submission | Gradescope https://www.gradescope.com/courses/425958/assignm...
19 of 25 7/3/23, 14:33
