81 lines
9.4 KiB
HTML
81 lines
9.4 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Function MERGE</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="f_concat.htm">
|
|
<LINK REL=UP HREF="c_sequen.htm">
|
|
<LINK REL=NEXT HREF="f_rm_rm.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="f_concat.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="c_sequen.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="f_rm_rm.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
<A NAME="merge"><I>Function</I> <B>MERGE</B></A> <P>
|
|
<P><B>Syntax:</B><P>
|
|
<P>
|
|
|
|
<B>merge</B> <I>result-type sequence-1 sequence-2 predicate <TT>&key</TT> key</I> => <I>result-sequence</I><P>
|
|
<P>
|
|
<P><B>Arguments and Values:</B><P>
|
|
<P>
|
|
<I>result-type</I>---a <A REL=DEFINITION HREF="t_seq.htm#sequence"><B>sequence</B></A> <A REL=DEFINITION HREF="26_glo_t.htm#type_specifier"><I>type specifier</I></A>. <P>
|
|
<I>sequence-1</I>---a <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A>. <P>
|
|
<I>sequence-2</I>---a <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A>. <P>
|
|
<I>predicate</I>---a <A REL=DEFINITION HREF="26_glo_d.htm#designator"><I>designator</I></A> for a <A REL=DEFINITION HREF="26_glo_f.htm#function"><I>function</I></A> of two arguments that returns a <A REL=DEFINITION HREF="26_glo_g.htm#generalized_boolean"><I>generalized boolean</I></A>. <P>
|
|
<I>key</I>---a <A REL=DEFINITION HREF="26_glo_d.htm#designator"><I>designator</I></A> for a <A REL=DEFINITION HREF="26_glo_f.htm#function"><I>function</I></A> of one argument, or <A REL=DEFINITION HREF="a_nil.htm#nil"><B>nil</B></A>. <P>
|
|
<I>result-sequence</I>---a <A REL=DEFINITION HREF="26_glo_p.htm#proper_sequence"><I>proper sequence</I></A> of <A REL=DEFINITION HREF="26_glo_t.htm#type"><I>type</I></A> <I>result-type</I>. <P>
|
|
<P><B>Description:</B><P>
|
|
<P>
|
|
Destructively merges <I>sequence-1</I> with <I>sequence-2</I> according to an order determined by the <I>predicate</I>. <A REL=DEFINITION HREF="#merge"><B>merge</B></A> determines the relationship between two elements by giving keys extracted from the sequence elements to the <I>predicate</I>. <P>
|
|
The first argument to the <I>predicate</I> function is an element of <I>sequence-1</I> as returned by the <I>key</I> (if supplied); the second argument is an element of <I>sequence-2</I> as returned by the <I>key</I> (if supplied). <I>Predicate</I> should return <A REL=DEFINITION HREF="26_glo_t.htm#true"><I>true</I></A> if and only if its first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then <I>predicate</I> should return <A REL=DEFINITION HREF="26_glo_f.htm#false"><I>false</I></A>. <A REL=DEFINITION HREF="#merge"><B>merge</B></A> considers two elements <TT>x</TT> and <TT>y</TT> to be equal if <TT>(funcall predicate x y)</TT> and <TT>(funcall predicate y x)</TT> both <A REL=DEFINITION HREF="26_glo_y.htm#yield"><I>yield</I></A> <A REL=DEFINITION HREF="26_glo_f.htm#false"><I>false</I></A>. <P>
|
|
The argument to the <I>key</I> is the <I>sequence</I> element. Typically, the return value of the <I>key</I> becomes the argument to <I>predicate</I>. If <I>key</I> is not supplied or <A REL=DEFINITION HREF="a_nil.htm#nil"><B>nil</B></A>, the sequence element itself is used. The <I>key</I> may be executed more than once for each <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A> <A REL=DEFINITION HREF="26_glo_e.htm#element"><I>element</I></A>, and its side effects may occur in any order. <P>
|
|
If <I>key</I> and <I>predicate</I> return, then the merging operation will terminate. The result of merging two <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequences</I></A> <TT>x</TT> and <TT>y</TT> is a new <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A> of type <I>result-type</I> <TT>z</TT>, such that the length of <TT>z</TT> is the sum of the lengths of <TT>x</TT> and <TT>y</TT>, and <TT>z</TT> contains all the elements of <TT>x</TT> and <TT>y</TT>. If <TT>x1</TT> and <TT>x2</TT> are two elements of <TT>x</TT>, and <TT>x1</TT> precedes <TT>x2</TT> in <TT>x</TT>, then <TT>x1</TT> precedes <TT>x2</TT> in <TT>z</TT>, and similarly for elements of <TT>y</TT>. In short, <TT>z</TT> is an interleaving of <TT>x</TT> and <TT>y</TT>. <P>
|
|
If <TT>x</TT> and <TT>y</TT> were correctly sorted according to the <I>predicate</I>, then <TT>z</TT> will also be correctly sorted. If <TT>x</TT> or <TT>y</TT> is not so sorted, then <TT>z</TT> will not be sorted, but will nevertheless be an interleaving of <TT>x</TT> and <TT>y</TT>. <P>
|
|
The merging operation is guaranteed stable; if two or more elements are considered equal by the <I>predicate</I>, then the elements from <I>sequence-1</I> will precede those from <I>sequence-2</I> in the result. <P>
|
|
<I>sequence-1</I> and/or <I>sequence-2</I> may be destroyed. <P>
|
|
If the <I>result-type</I> is a <A REL=DEFINITION HREF="26_glo_s.htm#subtype"><I>subtype</I></A> of <A REL=DEFINITION HREF="t_list.htm#list"><B>list</B></A>, the result will be a <A REL=DEFINITION HREF="26_glo_l.htm#list"><I>list</I></A>. <P>
|
|
If the <I>result-type</I> is a <A REL=DEFINITION HREF="26_glo_s.htm#subtype"><I>subtype</I></A> of <A REL=DEFINITION HREF="t_vector.htm#vector"><B>vector</B></A>, then if the implementation can determine the element type specified for the <I>result-type</I>, the element type of the resulting array is the result of <I>upgrading</I> that element type; or, if the implementation can determine that the element type is unspecified (or <TT>*</TT>), the element type of the resulting array is <A REL=DEFINITION HREF="t_t.htm#t"><B>t</B></A>; otherwise, an error is signaled. <P>
|
|
<P><B>Examples:</B><P>
|
|
|
|
<PRE>
|
|
(setq test1 (list 1 3 4 6 7))
|
|
(setq test2 (list 2 5 8))
|
|
(merge 'list test1 test2 #'<) => (1 2 3 4 5 6 7 8)
|
|
(setq test1 (copy-seq "BOY"))
|
|
(setq test2 (copy-seq :nosy"))
|
|
(merge 'string test1 test2 #'char-lessp) => "BnOosYy"
|
|
(setq test1 (vector ((red . 1) (blue . 4))))
|
|
(setq test2 (vector ((yellow . 2) (green . 7))))
|
|
(merge 'vector test1 test2 #'< :key #'cdr)
|
|
=> #((RED . 1) (YELLOW . 2) (BLUE . 4) (GREEN . 7))
|
|
</PRE>
|
|
</TT>
|
|
<PRE>
|
|
(merge '(vector * 4) '(1 5) '(2 4 6) #'<) should signal an error
|
|
</PRE>
|
|
</TT> <P>
|
|
<P><B>Affected By:</B> None.
|
|
<P>
|
|
<P><B>Exceptional Situations:</B><P>
|
|
<P>
|
|
An error must be signaled if the <I>result-type</I> is neither a <A REL=DEFINITION HREF="26_glo_r.htm#recognizable_subtype"><I>recognizable subtype</I></A> of <A REL=DEFINITION HREF="t_list.htm#list"><B>list</B></A>, nor a <A REL=DEFINITION HREF="26_glo_r.htm#recognizable_subtype"><I>recognizable subtype</I></A> of <A REL=DEFINITION HREF="t_vector.htm#vector"><B>vector</B></A>. <P>
|
|
An error of <A REL=DEFINITION HREF="26_glo_t.htm#type"><I>type</I></A> <A REL=DEFINITION HREF="e_tp_err.htm#type-error"><B>type-error</B></A> should be signaled if <I>result-type</I> specifies the number of elements and the sum of the lengths of <I>sequence-1</I> and <I>sequence-2</I> is different from that number. <P>
|
|
<P><B>See Also:</B><P>
|
|
<P>
|
|
<A REL=DEFINITION HREF="f_sort_.htm#sort"><B>sort</B></A>, <A REL=DEFINITION HREF="f_sort_.htm#stable-sort"><B>stable-sort</B></A>, <A REL=CHILD HREF="03_ba.htm">Section 3.2.1 (Compiler Terminology)</A>, <A REL=CHILD HREF="03_f.htm">Section 3.6 (Traversal Rules and Side Effects)</A> <P>
|
|
<P><B>Notes:</B> None.
|
|
<P>
|
|
<P><HR>The following <A REL=META HREF="../Front/X3J13Iss.htm">X3J13 cleanup issues</A>, <I>not part of the specification</I>, apply to this section:<P><UL><LI> <A REL=CHILD HREF="../Issues/iss240.htm">MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE</A><LI> <A REL=CHILD HREF="../Issues/iss083.htm">CONSTANT-MODIFICATION:DISALLOW</A><LI> <A REL=CHILD HREF="../Issues/iss302.htm">SEQUENCE-TYPE-LENGTH:MUST-MATCH</A><LI> <A REL=CHILD HREF="../Issues/iss073.htm">CONCATENATE-SEQUENCE:SIGNAL-ERROR</A><P></UL><HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|