<HTML> <HEAD> <!-- Created by texi2html 1.56k + clip patches and <A href="http://www.clip.dia.fi.upm.es/Software">lpdoc</A> from ciao.texi on 28 January 2007 --> <LINK rel="stylesheet" href="ciao.css" type="text/css"> <TITLE>The Ciao Prolog System - Sorting lists</TITLE> </HEAD> <BODY> Go to the <A HREF="ciao_1.html">first</A>, <A HREF="ciao_48.html">previous</A>, <A HREF="ciao_50.html">next</A>, <A HREF="ciao_241.html">last</A> section, <A HREF="ciao_toc.html">table of contents</A>. <P><HR><P> <H1><A NAME="SEC234" HREF="ciao_toc.html#TOC234">Sorting lists</A></H1> <P> <A NAME="IDX3228"></A> <P> <STRONG>Author(s):</STRONG> Richard A. O'Keefe. All changes by UPM CLIP Group.. <P> <STRONG>Version:</STRONG> 1.9#210 (2003/12/21, 2:12:13 CET) <P> This module implements some sorting list predicates. <UL> <LI><A HREF="ciao_49.html#SEC235">Usage and interface (sort)</A> <LI><A HREF="ciao_49.html#SEC236">Documentation on exports (sort)</A> <LI><A HREF="ciao_49.html#SEC237">Documentation on internals (sort)</A> </UL> <H2><A NAME="SEC235" HREF="ciao_toc.html#TOC235">Usage and interface (<CODE>sort</CODE>)</A></H2> <div class="cartouche"> <UL> <LI><STRONG>Library usage:</STRONG> <CODE>:- use_module(library(sort)).</CODE> <LI><STRONG>Exports:</STRONG> <UL> <LI><EM>Predicates:</EM> <A NAME="IDX3229"></A> <CODE>sort/2</CODE>, <A NAME="IDX3230"></A> <CODE>keysort/2</CODE>. <LI><EM>Regular Types:</EM> <A NAME="IDX3231"></A> <CODE>keylist/1</CODE>. </UL> </UL> </div class="cartouche"> <H2><A NAME="SEC236" HREF="ciao_toc.html#TOC236">Documentation on exports (<CODE>sort</CODE>)</A></H2> <P> <A NAME="IDX3232"></A> <A NAME="IDX3233"></A> <DL> <DT><span class="define">PREDICATE:</span> <B>sort/2:</B> <DD><A NAME="IDX3234"></A> <P> <CODE>sort(List1, List2)</CODE> <P> The elements of <CODE>List1</CODE> are sorted into the standard order (see section <A HREF="ciao_21.html#SEC144">Comparing terms</A>) and any identical elements are merged, yielding <CODE>List2</CODE>. The time and space complexity of this operation is at worst <CODE>O(N lg N)</CODE> where <CODE>N</CODE> is the length of <CODE>List1</CODE>. <P> <STRONG>Usage:</STRONG> <CODE>sort(+list, ?list)</CODE> <UL> <LI><EM>Description:</EM> <CODE>List2</CODE> is the sorted list corresponding to <CODE>List1</CODE>. <LI><EM>The following properties hold globally:</EM> This predicate is understood natively by CiaoPP. (<CODE>basic_props:native/1</CODE>) </UL> </DL> <P> <A NAME="IDX3235"></A> <A NAME="IDX3236"></A> <DL> <DT><span class="define">PREDICATE:</span> <B>keysort/2:</B> <DD><A NAME="IDX3237"></A> <P> <CODE>keysort(List1, List2)</CODE> <P> <CODE>List1</CODE> is sorted into order according to the value of the <EM>keys</EM> of its elements, yielding the list <CODE>List2</CODE>. No merging takes place. This predicate is <EM>stable</EM>, i.e., if an element <CODE>A</CODE> occurs before another element <CODE>B</CODE> <EM>with the same key</EM> in the input, then <CODE>A</CODE> will occur before <CODE>B</CODE> also in the output. The time and space complexity of this operation is at worst <CODE>O(N lg N)</CODE> where <CODE>N</CODE> is the length of <CODE>List1</CODE>. <P> <STRONG>Usage:</STRONG> <CODE>keysort(+keylist, ?keylist)</CODE> <UL> <LI><EM>Description:</EM> <CODE>List2</CODE> is the (key-)sorted list corresponding to <CODE>List1</CODE>. <LI><EM>The following properties hold globally:</EM> This predicate is understood natively by CiaoPP. (<CODE>basic_props:native/1</CODE>) </UL> </DL> <P> <A NAME="IDX3238"></A> <A NAME="IDX3239"></A> <DL> <DT><span class="define">REGTYPE:</span> <B>keylist/1:</B> <DD><A NAME="IDX3240"></A> <P> <STRONG>Usage:</STRONG> <CODE>keylist(L)</CODE> <UL> <LI><EM>Description:</EM> <CODE>L</CODE> is a list of pairs of the form <CODE>Key-Value</CODE>. </UL> </DL> <H2><A NAME="SEC237" HREF="ciao_toc.html#TOC237">Documentation on internals (<CODE>sort</CODE>)</A></H2> <P> <A NAME="IDX3241"></A> <A NAME="IDX3242"></A> <DL> <DT><span class="define">REGTYPE:</span> <B>keypair/1:</B> <DD><A NAME="IDX3243"></A> <P> <STRONG>Usage:</STRONG> <CODE>keypair(P)</CODE> <UL> <LI><EM>Description:</EM> <CODE>P</CODE> is a pair of the form "<CODE>K-_</CODE>", where <CODE>K</CODE> is considered the <EM>key</EM>. </UL> </DL> <P><HR><P> Go to the <A HREF="ciao_1.html">first</A>, <A HREF="ciao_48.html">previous</A>, <A HREF="ciao_50.html">next</A>, <A HREF="ciao_241.html">last</A> section, <A HREF="ciao_toc.html">table of contents</A>. </BODY> </HTML>