User Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cl:functions:merge [2019/07/14 17:00]
cl:functions:merge [2019/10/17 13:00] (current)
Line 1: Line 1:
 +====== Function MERGE ======
 +
 +====Syntax====
 +  * **merge** //​result-type//​ //​sequence-1//​ //​sequence-2//​ //​predicate//​ ''&​key''​ //key// → //​result-sequence//​
 +
 +====Arguments and Values====
 +  * //​result-type//​ - a **[[CL:​Types:​sequence]]** //​[[CL:​Glossary:​type specifier]]//​.
 +  * //​sequence-1//​ - a //​[[CL:​Glossary:​sequence]]//​.
 +  * //​sequence-2//​ - a //​[[CL:​Glossary:​sequence]]//​.
 +  * //​predicate//​ - a //​[[CL:​Glossary:​designator]]//​ for a //​[[CL:​Glossary:​function]]//​ of two arguments that returns a //​[[CL:​Glossary:​generalized boolean]]//​.
 +  * //key// - a //​[[CL:​Glossary:​designator]]//​ for a //​[[CL:​Glossary:​function]]//​ of one argument, or **[[CL:​Constant Variables:​nil]]**.
 +  * //​result-sequence//​ - a //​[[CL:​Glossary:​proper sequence]]//​ of //​[[CL:​Glossary:​type]]//​ //​result-type//​.
 +
 +====Description====
 +Destructively merges //​sequence-1//​ with //​sequence-2//​ according to an order determined by the //​predicate//​. **merge** determines the relationship between two elements by giving keys extracted from the sequence elements to the //​predicate//​.
 +
 +The first argument to the //​predicate//​ function is an element of //​sequence-1//​ as returned by the //key// (if supplied); the second argument is an element of //​sequence-2//​ as returned by the //key// (if supplied). //​Predicate//​ should return //​[[CL:​Glossary:​true]]//​ 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 //​predicate//​ should return //​[[CL:​Glossary:​false]]//​. **merge** considers two elements //x// and //y// to be equal if ''​([[CL:​Functions:​funcall]] //​predicate//​ //x// //​y//​)''​ and ''​([[CL:​Functions:​funcall]] //​predicate//​ //y// //​x//​)''​ both //​[[CL:​Glossary:​yield]]//​ //​[[CL:​Glossary:​false]]//​.
 +
 +The argument to the //key// is the //​sequence//​ element. Typically, the return value of the //key// becomes the argument to //​predicate//​. If //key// is not supplied or **[[CL:​Constant Variables:​nil]]**,​ the sequence element itself is used. The //key// may be executed more than once for each //​[[CL:​Glossary:​sequence]]//​ //​[[CL:​Glossary:​element]]//,​ and its side effects may occur in any order.
 +
 +If //key// and //​predicate//​ return, then the merging operation will terminate. The result of merging two //​[[CL:​Glossary:​sequence|sequences]]//​ ''​x''​ and ''​y''​ is a new //​[[CL:​Glossary:​sequence]]//​ of type //​result-type//​ ''​z'',​ such that the length of ''​z''​ is the sum of the lengths of ''​x''​ and ''​y'',​ and ''​z''​ contains all the elements of ''​x''​ and ''​y''​. If ''​x1''​ and ''​x2''​ are two elements of ''​x'',​ and ''​x1''​ precedes ''​x2''​ in ''​x'',​ then ''​x1''​ precedes ''​x2''​ in ''​z'',​ and similarly for elements of ''​y''​. In short, ''​z''​ is an interleaving of ''​x''​ and ''​y''​.
 +
 +If ''​x''​ and ''​y''​ were correctly sorted according to the //​predicate//,​ then ''​z''​ will also be correctly sorted. If ''​x''​ or ''​y''​ is not so sorted, then ''​z''​ will not be sorted, but will nevertheless be an interleaving of ''​x''​ and ''​y''​.
 +
 +The merging operation is guaranteed stable; if two or more elements are considered equal by the //​predicate//,​ then the elements from //​sequence-1//​ will precede those from //​sequence-2//​ in the result.
 +
 +//​sequence-1//​ and/or //​sequence-2//​ may be destroyed.
 +
 +If the //​result-type//​ is a //​[[CL:​Glossary:​subtype]]//​ of **[[CL:​Types:​list]]**,​the result will be a //​[[CL:​Glossary:​list]]//​.
 +
 +If the //​result-type//​ is a //​[[CL:​Glossary:​subtype]]//​ of **[[CL:​Types:​vector]]**,​then if the implementation can determine the element type specified for the //​result-type//,​ the element type of the resulting array is the result of //​[[CL:​Glossary:​upgrade|upgrading]]//​ that element type; or, if the implementation can determine that the element type is unspecified (or ''​*''​),​ the element type of the resulting array is **[[CL:​Types:​t]]**;​ otherwise, an error is signaled.
 +
 +====Examples==== ​
 +<​blockquote> ​
 +([[CL:​Macros:​defparameter]] *test1* ([[CL:​Functions:​list]] 1 3 4 6 7)) *TEST1*
 +([[CL:​Macros:​defparameter]] *test2* ([[CL:​Functions:​list]] 2 5 8)) *TEST2*
 +(merge '​[[CL:​Types:​list]] *test1* *test2* #'​[[CL:​Functions:​math-less|<​]]) <r>(1 2 3 4 5 6 7 8) </r>
 +([[CL:​Macros:​setf]] *test1* ([[CL:​Functions:​copy-seq]] "​BOY"​)) ​
 +([[CL:​Macros:​setf]] *test2* ([[CL:​Functions:​copy-seq]] "​nosy"​)) ​
 +(merge '​[[CL:​Types:​string]] *test1* *test2* #'​[[CL:​Functions:​char-lessp]]) <​r>"​BnOosYy"​ </r>
 +([[CL:​Macros:​setf]] *test1* ([[CL:​Functions:​vector]] '(red . 1) '(blue . 4)))
 +([[CL:​Macros:​setf]] *test2* ([[CL:​Functions:​vector]] '​(yellow . 2) '​(green . 7)))
 +(merge '​[[CL:​Types:​vector]] *test1* *test2* #'​[[CL:​Functions:​math-less|<​]] :key #'​[[CL:​Functions:​cdr]]) ​
 +<​r>#​((RED . 1) (YELLOW . 2) (BLUE . 4) (GREEN . 7))</​r>​
 +(merge '​([[CL:​Types:​vector]] [[CL:​Types:​wildcard|*]] 4) '(1 5) '(2 4 6) #'​[[CL:​Functions:​math-less|<​]])
 +<​e>​Error:​ The length requested (5) does not match the type restriction in (VECTOR * 4).</​e>​
 +</​blockquote>​
 +
 +====Affected By====
 +None.
 +
 +====Exceptional Situations====
 +An error must be signaled if the //​result-type//​ is neither a //​[[CL:​Glossary:​recognizable subtype]]// of **[[CL:​Types:​list]]**,​ nor a //​[[CL:​Glossary:​recognizable subtype]]// of **[[CL:​Types:​vector]]**.
 +
 +An error of type **[[CL:​Types:​type-error]]** should be signaled if //​result-type//​ specifies the number of elements and the sum of the lengths of //​sequence-1//​ and //​sequence-2//​ is different from that number.
 +
 +====See Also====
 +  * **[[CL:​Functions:​sort|Function SORT]]**
 +  * **[[CL:​Functions:​stable-sort|Function STABLE-SORT]]**
 +  * {\secref\ConstantModification}
 +  * {\secref\TraversalRules}
 +
 +====Notes====
 +None.
 +
 +\issue{CONCATENATE-SEQUENCE:​SIGNAL-ERROR} \issue{SEQUENCE-TYPE-LENGTH:​MUST-MATCH} \issue{CONSTANT-MODIFICATION:​DISALLOW} \issue{MAPPING-DESTRUCTIVE-INTERACTION:​EXPLICITLY-VAGUE} \issue{CONCATENATE-SEQUENCE:​SIGNAL-ERROR} \issue{CONCATENATE-SEQUENCE:​SIGNAL-ERROR} \issue{SEQUENCE-TYPE-LENGTH:​MUST-MATCH}