<p>
<h1>Working With Lists</h1>
<p>
The basic workhorse of most programmers is the list.  Again, unlike
many languages <em>Mercury</em> doesn't assume that there's anything special
about lists and they are defined entirely within the library module
<tt>list</tt>.  In the interface section of the <tt>list</tt> library we see
<p><center><table border=1 width=90%><tr><td><pre>

:- type list(T) ---> [] ; [T | list(T)].
</pre></tr></table></center><p>
This is a <em>type declaration</em> (about more of which later) which says
that a list of things with type <tt>T</tt> is either empty, <tt>[]</tt>, or a
structure <tt>[T | list(T)]</tt> whose first argument is a <tt>T</tt> and whose
second argument is another list of <tt>T</tt>s.  Here are some examples,
along with the same using some syntactic sugar on the right:
<p><center><table border=1 width=90%><tr><td><pre>

[1 | []]             = [1]              % a list(int)
["hi" | ["ho" | []]] = ["hi", "ho"]     % a list(string)
[a | [b | [c | []]]] = [a,b,c]          % a list(char)
</pre></tr></table></center><p>
By the way, anything from a <tt>%</tt> to the end of the line is a comment.
<p>
We can look inside a list using <em>pattern matching</em>.  If <tt>L</tt>
is a variable bound to some <tt>list(T)</tt> then
<p><center><table border=1 width=90%><tr><td><pre>

        L = []
</pre></tr></table></center><p>
will succeed iff <tt>L</tt> is the empty list.  On the other hand
<p><center><table border=1 width=90%><tr><td><pre>

        [Hd | Tl] = L
</pre></tr></table></center><p>
will succeed, binding <tt>Hd</tt> to the <em>head</em> of <tt>L</tt> and <tt>Tl</tt> to its
<em>tail</em> -- iff <tt>L</tt> is a non-empty list.  Of course, the type of
<tt>Hd</tt> is simply <tt>T</tt> and the type of <tt>Tl</tt> is <tt>list(T)</tt>.  Observe
that which side of <tt>=/2</tt> we put <tt>L</tt> makes no difference
whatsoever: as you may be getting the impression, <em>Mercury</em> strives to
be as close to mathematical form as possible.
<p>
Let's have a look at some examples.  Say we want to calculate the
length of a list.  We might write
<p><center><table border=1 width=90%><tr><td><pre>

        :- import_module list, int.
<p>
        :- pred length(list(T), int).
        :- mode length(in, out) is det.
<p>
        length(L, N) :-
                (
                        L = []
                        N = 0
                ;
                        L = [_Hd | Tl],
                        length(Tl, N0),
                        N = N0 + 1
                ).
</pre></tr></table></center><p>
The definition states that the length of the empty list <tt>[]</tt> is
zero and that the length of a non-empty list <tt>[Hd | Tl]</tt> is one plus
the length of its tail, <tt>Tl</tt>.
<p>
There are a number of new things in here, so let's take a closer look.