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
|
name = 'conc/3'
slug = 'concatenate two lists'
description = '''\
<p><code>conc(L1, L2, L)</code>: the list <code>L</code> is obtained by appending the elements of <code>L2</code> to <code>L1</code>.</p>
<pre>
?- conc([1,2], [3,4], X).
X = [1,2,3,4].
?- conc(X, [], [1,2,3]).
X = [1,2,3].
</pre>'''
plan = ['''\
<p><img src="[%@resource plan.svg%]" /></p>
''', '''\
<p>Let's start with an easy question. What do I get if I concatenate an empty list and a list <code>L2</code>?</p>
''', '''\
<p>Now, assume that the first list has exactly one element. Let's temporarily take it out which leaves us
with an empty list. But wait! Isn't this situation now similar to the one we dealt with before? Of course, we just
reduced the problem into a smaller one (by one element smaller). Let recursion solve this smaller problem. Just don't
forget to expand the recursion's result with the element you have taken out at the beginning...</p>
''', '''\
<p>Declarative/logic reasoning: Assume the first list <code>L1</code> has head <code>H</code> and tail
<code>T</code>. If the recursive result of concatenating <code>T</code> and <code>L2</code> is some list
<code>L3</code>, and if we add element <code>H</code> at the beginning of list <code>L3</code>, what do we get?
A concatenation of <code>L1</code> and <code>L2</code>!</p>
''']
hint = {
'eq_instead_of_equ': '''\
<p>The operator <code>==</code> is "stricter" than operator <code>=</code> in the sense that
for the latter it is enough to be able to make the two operands equal (unification). Perhaps by using <code>=</code>
you can make the predicate <code>conc/3</code> more general (e.g. able to work with output arguments becoming inputs).</p>
<p>Of course, you can also solve the exercise without explicit use of either of these two operators, just
remember that unification is implicitly performed with the predicate's arguments (head of clause).</p>
''',
'eq_instead_of_equ_markup': '''\
<p>Perhaps the operator for unification (=) would be better?</p>
''',
'base_case': '''\
<p>Did you think of a base case? What is the simplest possible case?
What's the answer if, for example, the first list is empty? (Just the first list should be empty,
the second one can be arbitrary.)</p>
''',
'base_case_arbitrary': '''\
<p>How can the result of concatenating two lists be an arbitrary list (a variable without an assigned value)?</p>
<p>If your base case is similar to <code>conc([], L, _)</code>,
then you should rethink it: what is the result of the concatenation, what do you return as the result?
The base case <em>always</em> fully specifies the result, usually there are no unknowns (<code>_</code>
or variables without assigned values) in what is being returned as the result.</p>
''',
'predicate_always_false': '''\
<p>It seems your predicate is <emph>always</emph> "false". Did you give it the correct name,
or is it perhaps misspelled?</p>
<p>If the name is correct, check whether something else is misspelled, perhaps there is a full stop instead of
a comma or vice versa, or maybe you typed a variable name in lowercase?</p>
<p>It is, of course, also possible that your conditions are too restrictive, or even impossible to satisfy
(as would be, for example, the condition that an empty list <code>[]</code> is equal to a list with
exactly three elements <code>[A,B,C]</code>, or something similarly impossible).</p>
''',
'timeout': '''\
<p>Is there an infinite recursion at work here? How will it ever stop?</p>
<p>Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?
Are you maybe reducing the first list, but your base case stops with an empty second list (or vice versa)?</p>
''',
'second_list_iteration': '''\
<p>It seems you're processing (reducing) the second list. The mechanism at work is correct, however,
the final ordering of the elements is not. It's better to process the first list in this way and
leave the second one as is.</p>
<p>There's another reason to process the first list: in this way the solution of this essential exercise
will be the same for everyone, and we'll be able to use <code>conc/3</code> in a standardised way. This
will be very important later on.</p>
''',
'insertion_into_second_list': '''
<p>Is your recursive call of the form <code>conc(T, [H|L2], ...)</code>?
Don't insert the first list's head into the second list as this will result in the wrong ordering
of the elements. Let the recursion alone take care of concatenating the first list's tail
<code>T</code> with the second list <code>L2</code>, and then, when returning the complete result,
add the first list's head <code>H</code> into its proper place.</p>
''',
'two_heads': '''\
<p>Do you really need two list heads? Are you trying to reduce both lists? This is not a good idea, it is
difficult to solve the exercise in this way. Rather simply reduce the first list only, and leave the
other list as is.</p>
''',
'two_heads_markup': '''\
<p>Do you really need two list heads?</p>
''',
'forcing_result_onto_recursion': '''
<p>Don't force the result onto recursion, don't tell it what it should return. Just assume it will do its job.
If this assumption is correct, then the rule will work for a larger case.</p>
<p>Is your recursive call of the form <code>conc(T, L2, [H|...])</code>? This forces the recursive call to
<em>return</em> the head at the start of the concatenated list. But it doesn't know of this head, because you just
took it away! Inserting the head into the result, returned by the recursive call, is your job. To put it shortly,
insert <code>H</code> outside of the recursive call.</p>
''',
'final_hint': '''\
<p>Predicate <code>conc/3</code> will be useful for much more than just concatenating two lists.
Among other things it can be used "in the other direction" -- for dividing a list into two parts. Try the
following queries:</p>
<p><code>?- conc(L1, L2, [a,b,c,d]).</code></p>
<p><code>?- conc([X,Y], L2, [a,b,c,d,e,f]).</code></p>
<p>Did you notice that the second query returned the first two elements from the list <code>[a,b,c,d,e,f]</code>?</p>
<p>Furthermore, <code>conc/3</code> is useful to search for patterns in a list, e.g.:</p>
<p><code>?- conc(_, [X,X|_], [a,b,c,c,d,e,f,f,g,h,h]).</code></p>
<p>Right, this query finds all possibilities where two identical elements appear one after the other in a list
(pattern X,X). Basically the query said that "there are some elements (possibly zero) in front, then follow two
identical elements, and then again some elements (possibly zero) at the end."</p>
<p>There are many other usages of <code>conc/3</code>, you will discover them along the way.</p>
''',
}
|
