title: Implementing "last" in Prolog
body: <p>I am trying to get a feel for Prolog programming by going through Ulle Endriss' <a href="http://staff.science.uva.nl/~ulle/teaching/prolog/prolog.pdf" rel="nofollow noreferrer">lecture notes</a>.  When my solution to an exercise does not behave as expected, I find it difficult to give a good explanation.  I think this has to do with my shaky understanding of the way Prolog evaluates expressions.</p>
  
  <p>Exercise 2.6 on page 20 calls for a recursive implementation of a predicate <code>last1</code> which behaves like the built-in predicate <code>last</code>.  My attempt is as follows:</p>
  
  <blockquote>
  <pre><code>last1([_ | Rest], Last) :- last1(Rest, Last).
  last1([Last], Last).
  </code></pre>
  </blockquote>
  
  <p>It gives the correct answer, but for lists with more than one element, I have to key in the semicolon to terminate the query.  This makes <code>last1</code> different from the built-in <code>last</code>.</p>
  
  <pre><code>?- last1([1], Last).
  Last = 1.
  
  ?- last1([1, 2], Last).
  Last = 2 ;
  false.
  </code></pre>
  
  <p>If I switch the order in which I declared the rule and fact, then I need to key in the semicolon in both cases.</p>
  
  <p>I think I know why Prolog thinks that <code>last1</code> may have one more solution (thus the semicolon).  I imagine it follows the evaluation sequence</p>
  
  <pre><code>last1([1, 2], Last).
  ==&gt;  last1([2], Last).
  ==&gt;  last1([], Last).    OR    Last = 2.
  ==&gt;  false    OR    Last = 2.
  </code></pre>
  
  <p>That seems to suggest that I should look for a way to avoid matching <code>Rest</code> with <code>[]</code>.  Regardless, I have no explanation why switching the order of declaration ought to have any effect at all.</p>
  
  <p><strong>Question 1:</strong>  What is the correct explanation for the behavior of <code>last1</code>?</p>
  
  <p><strong>Question 2:</strong>  How can I implement a predicate <code>last1</code> which is indistinguishable from the built-in <code>last</code>?</p>