name = 'isort/2'
slug = 'sort a list using insertion sort'

description = '''\
<p><code>isort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>sins/3</code> to implement insertion sort.</p>
<pre>
?- isort([2,3,1,5,4], L).
  L = [1,2,3,4,5].
</pre>'''

plan = ['''\
<p>When going through the list (actually when returning from recursion) at every step insert the current element
in its proper position.</p>
''', '''\
<p>When going through the list at every step take away the head (it's stored on stack), while its tail goes
into recursion (the problem/list is shorter, so this is possible). The recursion returns the <em>sorted</em>
tail, and all that's left for you to do is to put the previously taken away head into its proper place in the
sorted tail. Of course you can reuse some previous exercise for this task.</p>
''', '''\
<p>If list <code>L</code> is composed of head <code>H</code> and tail <code>T</code> and if we assume that
tail <code>T</code> is correctly sorted into <code>SortedTail</code> by recursion, and if head <code>H</code>
is inserted into its proper place within <code>SortedTail</code>, then we get the whole list <code>L</code>
properly sorted.</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).</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? Which list can you sort without any effort whatsoever?</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 <em>always</em> "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 <code>X</code> is <em>simultaneously</em> smaller and greater than
<code>Y</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>
''',

    'min_used': '''\
<p>Try solving this exercise without using the predicate <code>min/2</code>.</p>
''',
}