name = 'insert/3'
slug = 'insert an element into list'

description = '''\
<p><code>insert(X, L1, L2)</code>: the list <code>L2</code> is obtained from <code>L1</code> by inserting the element <code>X</code> at arbitrary position.</p>
<pre>
?- insert(1, [2,3], L).
  L = [1,2,3] ;
  L = [2,1,3] ;
  L = [2,3,1].
</pre>'''

plan = ['''
<p><img src="[%@resource plan.svg%]" /></p>
<p>Where in the list can we insert a new element <code>X</code>? Remember that a list has two parts: head and tail.
That means there are two possibilies. That's right, only two -- but in the tail we can again insert either as its
new head or into the tail of the tail. And so on. Recursion to the rescue!</p>
''', '''\
<p>What is the simplest option? Insert at the beginning!</p>
''', '''\
<p>How do I insert into the list's tail? Just divide the list into its head and tail, recursively (as
the problem is one element smaller now) insert into the tail, and at the end don't forget about the
head previously taken away.</p>
''', '''\
<p>Recursive step: if we assume <code>NewTail</code> is the tail with already inserted element <code>X</code>,
then <code>[H|NewTail]</code> is the whole list with element <code>X</code> inserted.</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>insert/3</code> more general (e.g. able to work with output arguments becoming inputs).
This might come in handy later on!</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><img src="[%@resource base_case.svg%]" /></p>
<p>Did you think of a base case? In which place in the list is it the easiest to insert a new element?</p>
''',

    'recursive_case': '''\
<p>The base case is ok. However, what about the general recursive case?</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?</p>
''',

    'ins_results_in_empty_list': '''\
<p>How can the result of the insertion be an empty list?</p>
<p>If that is your base case, rethink it! What is the result of the insertion?</p>
''',

    'ins_results_in_arbitrary_result': '''\
<p>How can the result of the insertion be an arbitrary list or an unassigned variable?</p>
<p>If that is your base case, rethink it! What is the result of the insertion?</p>
''',

    'lost_heads': '''\
<p><img src="[%@resource lost_heads.svg%]" /></p>
<p>The element has been successfully inserted, but all the others before it are lost, right?
Did you forget to put the head back at the front of the list after returning from recursion?</p>
<p>Try asking the following query and check <em>all</em> the solutions:</p>
<p><code>?- insert(q, [a,b,c,d], L).</code></p>
''',

    'leading_heads_all_x': '''\
<p><img src="[%@resource leading_heads_all_x.svg%]" /></p>
<p>Did you forget (copy/paste?) and used <code>[X|T]</code> instead of the more general <code>[H|T]</code>
in the recursive case?</p>
<p>Of the following two queries one works and the other doesn't.</p>
<p><code>?- insert(d, [d,d,d,d,e,f,g], L).</code></p>
<p><code>?- insert(d, [a,b,c,d,e,f,g], L).</code></p>
''',
}