name = 'last_elem/2'
slug = 'find last element in list'

description = '''\
<p><code>last_elem(L, E)</code>: <code>E</code> is the last element of list <code>L</code>.</p>
<pre>
?- last_elem([1,2,3], X).
  X = 3.
?- last_elem([3,2,X], 1).
  X = 1.
</pre>'''

plan = ['''\
<p>It's easy to access the first element in a list, but to get to the last element one needs to
recursively go through the whole list.</p>
''', '''\
<p>The list can be divided into its head and tail, and the search can proceed with the tail.
The problem is now smaller (the tail is shorter than the whole list), so we can use recursion.</p>
''', '''\
<p>If <code>X</code> is the last element of tail <code>T</code>, then <code>X</code> is also
the last element of the whole list that looks like <code>[H|T]</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>last_elem/2</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's the simplest possible case? What if the list contains only one element?</p>
''',

    '[]_should_not_succeed': '''\
<p>How did you succeed to find a last element in an empty list? You likely need a different base case.</p>
''',

    'list_returned': '''\
<p>You are returning a list instead of an element.</p>
''',

    'clumsy_conc_use': '''\
<p>Are you using <code>conc/3</code>? An interesting idea. Don't forget that the second list you're
concatenating must be <em>of length one</em> if you want to achieve the desired effect.
So a pattern of the form <code>[X]</code>, right?</p>
''',

    'unsuccessful_conc_use': '''\
<p>Are you using <code>conc/3</code>? An interesting idea; it is possible to solve in this way.
However, a bit of tweaking is still needed. Don't forget that <code>conc/3</code> has three arguments,
and all three are lists. Think about what kind of a pattern do you need...</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>
''',

    'final_hint': '''\
<p>Interesting fact: predicate <code>conc/3</code> can be used to search for patterns in lists. The last
element in a list is also a kind of pattern. What happens if we concatenate an arbitrary list <code>_</code>
and a list <em>of length one</em> (in this order)? A list of length one is of course written as
<code>[Element]</code>.</p>
<p>Try asking the following query:</p>
<p><code>?- conc(_, [Element], [a,b,c,d,e,f,q]).</code></p>
<p>So, can you now fetch the list's last element using <code>conc/3</code>? This will be very useful in
further exercises. On the other hand, of course, accessing the last element of a list is still quite
expensive, it's done in O(n) time. Therefore, if it's not important which element of a list is to be used,
or where in a list a new element is to be added, always work with the head.</p>
<p>And what does this query do? ;)</p>
<p><code>?- conc([a,b,c], [q], L).</code></p>
''',
}