<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.06-7 of 2001-11-14">
<TITLE>
List processing
</TITLE>
</HEAD>
<BODY TEXT=black BGCOLOR=white>
<A HREF="manual042.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual044.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66dbff"><DIV ALIGN=center><TABLE>
<TR><TD><FONT SIZE=4><B><A NAME="htoc200">7.20</A></B></FONT></TD>
<TD WIDTH="100%" ALIGN=center><FONT SIZE=4><B>List processing</B></FONT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><UL>
<LI><A HREF="manual043.html#toc159"> <TT>append/3</TT></A>
<LI><A HREF="manual043.html#toc160"> <TT>member/2</TT>,
<TT>memberchk/2</TT></A>
<LI><A HREF="manual043.html#toc161"> <TT>reverse/2</TT></A>
<LI><A HREF="manual043.html#toc162"> <TT>delete/3</TT>,
<TT>select/3</TT></A>
<LI><A HREF="manual043.html#toc163"> <TT>permutation/2</TT></A>
<LI><A HREF="manual043.html#toc164"> <TT>prefix/2</TT>,
<TT>suffix/2</TT></A>
<LI><A HREF="manual043.html#toc165"> <TT>sublist/2</TT></A>
<LI><A HREF="manual043.html#toc166"> <TT>last/2</TT></A>
<LI><A HREF="manual043.html#toc167"> <TT>length/2</TT></A>
<LI><A HREF="manual043.html#toc168"> <TT>nth/3</TT></A>
<LI><A HREF="manual043.html#toc169"> <TT>max_list/2</TT>,
<TT>min_list/2</TT>,
<TT>sum_list/2</TT></A>
<LI><A HREF="manual043.html#toc170"> <TT>sort/2</TT>,
<TT>sort0/2</TT>,
<TT>keysort/2</TT>
<TT>sort/1</TT>,
<TT>sort0/1</TT>,
<TT>keysort/1</TT></A>
</UL>
<BR>
These predicates manipulate lists. They are bootstrapped predicates (i.e.
written in Prolog) and no error cases are tested (for the moment). However,
since they are written in Prolog using other built-in predicates, some
errors can occur due to those built-in predicates.<BR>
<BR>
<A NAME="toc159"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc201">7.20.1</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>append/3</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
append(?list, ?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>append(List1, List2, List12)</TT> succeeds if the concatenation of the
list <TT>List1</TT> and the list <TT>List2</TT> is the list <TT>List12</TT>.
This predicate is re-executable on backtracking (e.g. if <TT>List12</TT> is
instantiated and both <TT>List1</TT> and <TT>List2</TT> are variable).<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc160"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc202">7.20.2</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>member/2</TT>,
<TT>memberchk/2</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
member(?term, ?list)<BR>
memberchk(?term, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>member(Element, List)</TT> succeeds if <TT>Element</TT> belongs to the
<TT>List</TT>. This predicate is re-executable on backtracking and can be
thus used to enumerate the elements of <TT>List</TT>.<BR>
<BR>
<TT>memberchk/2</TT> is similar to <TT>member/2</TT> but only succeeds once.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc161"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc203">7.20.3</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>reverse/2</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
reverse(?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>reverse(List1, List2)</TT> succeeds if <TT>List2</TT> unifies with the
list <TT>List1</TT> in reverse order.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc162"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc204">7.20.4</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>delete/3</TT>,
<TT>select/3</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
delete(?list, ?term, ?list)<BR>
select(?term, ?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>delete(List1, Element, List2)</TT> removes all occurrences of
<TT>Element</TT> in <TT>List1</TT> to provide <TT>List2</TT>. A strict term
equality is required, cf. <TT>(==)/2</TT> (section <A HREF="manual026.html#(==)/2">7.3.2</A>).<BR>
<BR>
<TT>select(Element, List1, List2)</TT> removes one occurrence of
<TT>Element</TT> in <TT>List1</TT> to provide <TT>List2</TT>. This predicate
is re-executable on backtracking.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc163"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc205">7.20.5</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>permutation/2</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
permutation(?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>permutation(List1, List2)</TT> succeeds if <TT>List2</TT>
is a permutation of the elements of <TT>List1</TT>. This predicate is
re-executable on backtracking.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc164"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc206">7.20.6</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>prefix/2</TT>,
<TT>suffix/2</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
prefix(?list, ?list)<BR>
suffix(?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>prefix(Prefix, List)</TT> succeeds if <TT>Prefix</TT> is a prefix of
<TT>List</TT>. This predicate is re-executable on backtracking.<BR>
<BR>
<TT>suffix(Suffix, List)</TT> succeeds if <TT>Suffix</TT> is a suffix of
<TT>List</TT>. This predicate is re-executable on backtracking.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc165"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc207">7.20.7</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>sublist/2</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
sublist(?list, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>sublist(List1, List2)</TT> succeeds if <TT>List2</TT> is a sub-list of
<TT>List1</TT>. This predicate is re-executable on backtracking.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc166"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc208">7.20.8</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>last/2</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
last(?list, ?term)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>last(List, Element)</TT> succeeds if <TT>Element</TT> is the last element
of <TT>List</TT>.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc167"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc209">7.20.9</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>length/2</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
length(?list, ?integer)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>length(List, Length)</TT> succeeds if <TT>Length</TT> is the length of
<TT>List</TT>.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc168"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc210">7.20.10</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>nth/3</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
nth(?integer, ?list, ?term)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>nth(N, List, Element)</TT> succeeds if the <TT>N</TT><EM>th</EM>
argument of <TT>List</TT> is <TT>Element</TT>.<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc169"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc211">7.20.11</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>max_list/2</TT>,
<TT>min_list/2</TT>,
<TT>sum_list/2</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
min_list(+list, ?number)<BR>
max_list(+list, ?number)<BR>
sum_list(+list, ?number)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>min_list(List, Min)</TT> succeeds if <TT>Min</TT> is the
smallest number in <TT>List</TT>.<BR>
<BR>
<TT>max_list(List, Max)</TT> succeeds if <TT>Max</TT> is the
largest number in <TT>List</TT>.<BR>
<BR>
<TT>sum_list(List, Sum)</TT> succeeds if <TT>Sum</TT> is the
sum of all the elements in <TT>List</TT>.<BR>
<BR>
<TT>List</TT> must be a list of arithmetic evaluable terms
(section <A HREF="manual029.html#Evaluation-of-an-arithmetic-expression">7.6.1</A>).<BR>
<BR>
<B>Errors</B><BR>
<BR>
None.<BR>
<BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicate.<BR>
<BR>
<A NAME="toc170"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc212">7.20.12</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>sort/2</TT>,
<TT>sort0/2</TT>,
<TT>keysort/2</TT>
<TT>sort/1</TT>,
<TT>sort0/1</TT>,
<TT>keysort/1</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<A NAME="sort/2"></A>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
sort(+list, ?list)<BR>
sort0(+list, ?list)<BR>
keysort(+list, ?list)<BR>
sort(+list)<BR>
sort0(+list)<BR>
keysort(+list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>sort(List1, List2)</TT> succeeds if <TT>List2</TT> is the
sorted list corresponding to <TT>List1</TT> where duplicate elements are
merged.<BR>
<BR>
<TT>sort0/2</TT> is similar to <TT>sort/2</TT> except that duplicate elements
are not merged.<BR>
<BR>
<TT>keysort(List1, List2)</TT> succeeds if <TT>List2</TT> is the
sorted list of <TT>List1</TT> according to the keys. The list <TT>List1</TT>
consists of items of the form <TT>Key-Value</TT>. These items are sorted
according to the value of <TT>Key</TT> yielding the <TT>List2</TT>. Duplicate
keys are not merged. This predicate is stable, i.e. if <TT>K-A</TT> occurs
before <TT>K-B</TT> in the input, then <TT>K-A</TT> will occur before
<TT>K-B</TT> in the output.<BR>
<BR>
<TT>sort/1</TT>, <TT>sort0/1</TT> and <TT>keysort/1</TT> are similar to
<TT>sort/2</TT>, <TT>sort0/2</TT> and <TT>keysort/2</TT> but achieve a sort
in-place destructing the original <TT>List1</TT> (this in-place assignment is
not undone at backtracking). The sorted list occupies the same memory space
as the original list (saving thus memory consumption).<BR>
<BR>
The time complexity of these sorts is <I>O</I>(<I>N log N</I>), <I>N</I> being the length of
the list to sort.<BR>
<BR>
These predicates refer to the standard ordering of terms
(section <A HREF="manual026.html#Standard-total-ordering-of-terms">7.3.1</A>). <BR>
<BR>
<B>Errors</B><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>List1</TT> is a partial list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>instantiation_error</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>List1</TT> is neither a partial list nor a list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, List1)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>List2</TT> is neither a partial list nor a list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, List2)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR></TABLE><BR>
<B>Portability</B><BR>
<BR>
GNU Prolog predicates.<BR>
<BR>
<HR SIZE=2>
Copyright (C) 1999-2002 Daniel Diaz
<BR>
<BR>
Verbatim copying and distribution of this entire article is permitted in any
medium, provided this notice is preserved. <BR>
<BR>
<A HREF="index.html#copyright">More about the copyright</A>
<HR>
<A HREF="manual042.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual044.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
