forked from mbg/uow-exam
-
Notifications
You must be signed in to change notification settings - Fork 2
/
q1.tex
148 lines (143 loc) · 5.14 KB
/
q1.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
%%% Question 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\question This question is about functional programming as a programming paradigm.
\begin{parts}
\part Reduce all of the following Haskell expressions to normal forms. Your answers \emph{must} include all reduction steps. No marks are awarded for answers which just state the normal form.
\begin{subparts}
\subpart[2] \haskellIn{not False && (True || False)} \droppoints
\begin{solution} \small
\begin{verbatim}
not False && (True || False)
=> True && (True || False)
=> True && True
=> True
\end{verbatim}
\end{solution}
\subpart[2] \haskellIn{filter (\x -> x /= 2 && x /= 6) [1..6]} \droppoints
\begin{solution} \small
\begin{verbatim}
filter (\x -> x /= 2 && x /= 6) [1..6]
== filter (\x -> x /= 2 && x /= 6) [1,2,3,4,5,6]
=> 1 : filter (\x -> x /= 2 && x /= 6) [2,3,4,5,6]
=> 1 : filter (\x -> x /= 2 && x /= 6) [3,4,5,6]
=> 1 : 3 : filter (\x -> x /= 2 && x /= 6) [4,5,6]
=> 1 : 3 : 4 : filter (\x -> x /= 2 && x /= 6) [5,6]
=> 1 : 3 : 4 : 5 : filter (\x -> x /= 2 && x /= 6) [6]
=> 1 : 3 : 4 : 5 : filter (\x -> x /= 2 && x /= 6) []
=> 1 : 3 : 4 : 5 : []
== [1,3,4,5]
\end{verbatim}
\end{solution}
\subpart[2] \haskellIn{if (odd 6) then [] else (drop 2 [1..5])} \droppoints
\begin{solution} \small
\begin{verbatim}
if (odd 6) then [] else (drop 2 [1..5])
== if (odd 6) then [] else (drop 2 [1,2,3,4,5])
=> if False then [] else (drop 2 [1,2,3,4,5])
=> drop 2 [1,2,3,4,5]
=> drop 1 [2,3,4,5]
=> drop 0 [3,4,5]
=> [3,4,5]
\end{verbatim}
\end{solution}
\subpart[2] \haskellIn{fmap toUpper "seal"} \droppoints
\begin{solution} \small
\begin{verbatim}
fmap toUpper "seal"
== fmap toUpper ['s', 'e', 'a', 'l']
=> toUpper 's' : fmap toUpper ['e', 'a', 'l']
=> 'S' : fmap toUpper ['e', 'a', 'l']
=> 'S' : toUpper 'e' : fmap toUpper ['a', 'l']
=> 'S' : 'E' : fmap toUpper ['a', 'l']
=> 'S' : 'E' : toUpper 'a' : fmap toUpper ['l']
=> 'S' : 'E' : 'A' : fmap toUpper ['l']
=> 'S' : 'E' : 'A' : toUpper 'l' : fmap toUpper []
=> 'S' : 'E' : 'A' : 'L' : fmap toUpper []
=> 'S' : 'E' : 'A' : 'L' : []
== ['S', 'E', 'A', 'L']
== "SEAL"
\end{verbatim}
\end{solution}
\subpart[2] \haskellIn{map (map snd) [[(4,'c')], [(8,'a'), (15,'r')], []]} \droppoints
\begin{solution} \small
\begin{verbatim}
map (map snd) [[(4,'c')], [(8,'a'), (15,'r')], []]
=> map snd [(4,'c')] :
map (map snd) [[(8,'a'), (15,'r')], []]
=> [snd (4,'c')] :
map (map snd) [[(8,'a'), (15,'r')], []]
=> ['c'] :
map (map snd) [[(8,'a'), (15,'r')], []]
=> ['c'] : map snd [(8,'a'), (15,'r')] :
map (map snd) [[]]
=> ['c'] : [snd (8,'a'), snd (15,'r')] :
map (map snd) [[]]
=> ['c'] : ['a', 'r'] : map (map snd) [[]]
=> ['c'] : ['a', 'r'] : map snd [] : map (map snd) []
=> ['c'] : ['a', 'r'] : [] : map (map snd) []
=> ['c'] : ['a', 'r'] : [] : []
== [['c'], ['a', 'r'], []]
== ["c","ar",""]
\end{verbatim}
\end{solution}
\end{subparts}
\part[3] Consider the following definition of the list difference operator \haskellIn{(\\)}:
\begin{minted}{haskell}
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ [] = xs
xs \\ (y:ys) = delete y (xs \\ ys)
\end{minted}
Define a function \haskellIn{diff} which is equivalent to \haskellIn{(\\)}, but is defined using \haskellIn{foldl} instead of explicit recursion. \droppoints
\begin{solution}
\emph{Application.} One possible answer is:
\begin{minted}{haskell}
diff = foldl (flip delete)
\end{minted}
\end{solution}
\begin{subparts}
\subpart[4] \label{part:strict} Trace how \haskellIn{diff "abbc" "bd"} would be evaluated in a language with \emph{call-by-value} semantics. \droppoints
\begin{solution}
\emph{Comprehension.}
\begin{small}
\begin{verbatim}
diff "abbc" "bd"
=> foldl (flip delete) "abbc" "bd"
=> foldl (flip delete) (flip delete "abbc" 'b') "d"
=> foldl (flip delete) "abc" "d"
=> foldl (flip delete) (flip delete "abc" 'd') ""
=> foldl (flip delete) "abc" ""
=> "abc"
\end{verbatim}
\end{small}
\end{solution}
\subpart[4] \label{part:lazy} Trace how \haskellIn{diff "abbc" "bd"} would be evaluated in a language with \emph{call-by-name} semantics. You should assume that the value of this expression is required by some other part of the program. \droppoints
\begin{solution} \emph{Comprehension.}
\begin{small}
\begin{verbatim}
diff "abbc" "bd"
=> foldl (flip delete) "abbc" "bd"
=> foldl (flip delete) (flip delete "abbc" 'b') "d"
=> foldl (flip delete) (flip delete
(flip delete "abbc" 'b') 'd') ""
=> flip delete (flip delete "abbc" 'b') 'd'
=> flip delete "abc" 'd'
=> "abc"
\end{verbatim}
\end{small}
\end{solution}
\subpart[4] Define a closed type family
\vspace*{0.2cm}
\begin{minted}{haskell}
Delete :: Nat -> [Nat] -> [Nat]
\end{minted}
\vspace*{0.2cm}
which removes the first occurrence of a type of kind \haskellIn{Nat} from a type-level list of types of kind \haskellIn{Nat}. For example, \haskellIn{Delete 'Zero ['Succ 'Zero, 'Zero, 'Zero]} should evaluate to \haskellIn{['Succ 'Zero, 'Zero]}. \droppoints
\begin{solution} \emph{Application.}
\begin{minted}{haskell}
type family Delete (a :: Nat) (xs :: [Nat]) :: [Nat] where
Delete a '[] = '[]
Delete a (a ': xs) = xs
Delete a (b ': xs) = b ': (Delete a xs)
\end{minted}
\end{solution}
\end{subparts}
\end{parts}