dict-sequences.tex 82 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537
  1. % -*- Mode: TeX -*-
  2. % Sequences
  3. % Sequence Mapping
  4. % Sequence Counting
  5. % Sequence Ordering
  6. % Sequence Search
  7. % Sequence Comparison
  8. % Sequence Substitution
  9. % Sequence Joining
  10. % Sequence Deletion
  11. %-------------------- Sequence Type --------------------
  12. %%% ========== SEQUENCE
  13. \begincom{sequence}\ftype{System Class}
  14. \label Class Precedence List::
  15. \typeref{sequence},
  16. \typeref{t}
  17. \label Description::
  18. \term{Sequences} are ordered collections of \term{objects},
  19. called the \term{elements} of the \term{sequence}.
  20. %% 2.15.0 26
  21. \Thetypes{vector} and \thetype{list} are \term{disjoint} \subtypesof{sequence},
  22. %The following is added to make an implicit vagueness explicit. -kmp 29-Mar-91
  23. but are not necessarily an \term{exhaustive partition} of \term{sequence}.
  24. When viewing a \term{vector} as a \term{sequence},
  25. only the \term{active} \term{elements} of that \term{vector}
  26. are considered \term{elements} of the \term{sequence};
  27. that is,
  28. \term{sequence} operations respect the \term{fill pointer}
  29. when given \term{sequences} represented as \term{vectors}.
  30. %% 2.4.0 2
  31. %% 2.4.0 7
  32. \endcom%{sequence}\ftype{System Class}
  33. %-------------------- Sequences --------------------
  34. %%% ========== COPY-SEQ
  35. \begincom{copy-seq}\ftype{Function}
  36. %KMP: It's too bad this function is not called copy-sequence.
  37. \label Syntax::
  38. \DefunWithValues copy-seq {sequence} {copied-sequence}
  39. \label Arguments and Values::
  40. \param{sequence}---a \term{proper sequence}.
  41. \param{copied-sequence}---a \term{proper sequence}.
  42. \label Description::
  43. %% 14.1.0 8
  44. Creates a copy of \param{sequence}. The \term{elements} of the new
  45. \term{sequence} are the \term{same} as the corresponding \term{elements} of
  46. the given \param{sequence}.
  47. %% Moon's suggested interpretation follows:
  48. If \param{sequence} is a \term{vector},
  49. the result is a \term{fresh} \term{simple array}
  50. of \term{rank} one
  51. that has the same \term{actual array element type} as \param{sequence}.
  52. If \param{sequence} is a \term{list},
  53. the result is a \term{fresh} \term{list}.
  54. %% End Moon's suggested interpretation.
  55. \label Examples::
  56. \code
  57. (setq str "a string") \EV "a string"
  58. (equalp str (copy-seq str)) \EV \term{true}
  59. (eql str (copy-seq str)) \EV \term{false}
  60. \endcode
  61. \label Side Effects:\None.
  62. %% Sandra thinks this is excessive.
  63. %Creates a new \term{sequence}.
  64. \label Affected By:\None.
  65. \label Exceptional Situations::
  66. \Lazychecktype{sequence}{a \term{proper sequence}}
  67. \label See Also::
  68. \funref{copy-list}
  69. \label Notes::
  70. From a functional standpoint,
  71. \code
  72. (copy-seq x) \EQ (subseq x 0)
  73. \endcode
  74. However, the programmer intent is typically very different in these two cases.
  75. \endcom
  76. %%% ========== ELT
  77. \begincom{elt}\ftype{Accessor}
  78. \label Syntax::
  79. \DefunWithValues elt {sequence index} {object}
  80. \Defsetf elt {sequence index} {new-object}
  81. \label Arguments and Values::
  82. \param{sequence}---a \term{proper sequence}.
  83. \param{index}---a \term{valid sequence index} for \param{sequence}.
  84. \param{object}---an \term{object}.
  85. \param{new-object}---an \term{object}.
  86. \label Description::
  87. %% 14.1.0 3
  88. \term{Accesses} the \term{element} of \param{sequence} specified by \param{index}.
  89. % No longer needed -- implied by "Access". -kmp 13-Jan-92
  90. % %% 14.1.0 5
  91. % \macref{setf} may be used with \funref{elt} to destructively replace
  92. % a \term{sequence} element with a new value.
  93. %Barmar thinks (and I agree) that this is redundant with the specification
  94. %of the argument type above.
  95. %
  96. % %% 14.1.0 4
  97. % \funref{elt} observes the \term{fill pointer} in those \term{vectors}
  98. % that have \term{fill pointers}.
  99. \label Examples::
  100. \code
  101. (setq str (copy-seq "0123456789")) \EV "0123456789"
  102. (elt str 6) \EV #\\6
  103. (setf (elt str 0) #\\#) \EV #\\#
  104. str \EV "#123456789"
  105. \endcode
  106. \label Side Effects:\None.
  107. \label Affected By:\None.
  108. \label Exceptional Situations::
  109. %% e.g., consider:
  110. % (LET ((X (NCONC (MAKE-LIST 1000 :INITIAL-ELEMENT 'A) '(B . C))))
  111. % (ELT X 1000))
  112. % => A
  113. \Lazychecktype{sequence}{a \term{proper sequence}}
  114. \Shouldchecktype{index}{a \term{valid sequence index} for \param{sequence}}
  115. \label See Also::
  116. \funref{aref},
  117. \funref{nth},
  118. \issue{CONSTANT-MODIFICATION:DISALLOW}
  119. {\secref\ConstantModification}
  120. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  121. \label Notes::
  122. \funref{aref} may be used to \term{access} \term{vector}
  123. elements that are beyond the \term{vector}'s \term{fill pointer}.
  124. \endcom
  125. %%% ========== FILL
  126. \begincom{fill}\ftype{Function}
  127. \label Syntax::
  128. \DefunWithValues fill {sequence item {\key} start end} {sequence}
  129. \label Arguments and Values::
  130. \param{sequence}---a \term{proper sequence}.
  131. \param{item}---a \term{sequence}.
  132. \issue{SUBSEQ-OUT-OF-BOUNDS}
  133. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  134. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  135. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  136. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  137. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  138. \label Description::
  139. %% 14.3.0 3
  140. Replaces the \term{elements} of \param{sequence}
  141. \term{bounded} by \param{start} and \param{end}
  142. with \param{item}.
  143. \label Examples::
  144. \code
  145. (fill (list 0 1 2 3 4 5) '(444)) \EV ((444) (444) (444) (444) (444) (444))
  146. (fill (copy-seq "01234") #\\e :start 3) \EV "012ee"
  147. (setq x (vector 'a 'b 'c 'd 'e)) \EV #(A B C D E)
  148. (fill x 'z :start 1 :end 3) \EV #(A Z Z D E)
  149. x \EV #(A Z Z D E)
  150. (fill x 'p) \EV #(P P P P P)
  151. x \EV #(P P P P P)
  152. \endcode
  153. \label Side Effects::
  154. \param{Sequence} is destructively modified.
  155. \label Affected By:\None.
  156. \label Exceptional Situations::
  157. \Lazychecktype{sequence}{a \term{proper sequence}}
  158. \Shouldchecktype{start}{a non-negative \term{integer}}
  159. \Shouldchecktype{end}{a non-negative \term{integer} or \nil}
  160. \label See Also::
  161. \funref{replace}, \funref{nsubstitute}
  162. \label Notes::
  163. {\tt (fill \param{sequence} \param{item}) \EQ
  164. (nsubstitute-if \param{item} (constantly t) \param{sequence})}
  165. \endcom
  166. %%% ========== MAKE-SEQUENCE
  167. \begincom{make-sequence}\ftype{Function}
  168. \label Syntax::
  169. \DefunWithValues make-sequence
  170. {result-type size {\key} initial-element}
  171. {sequence}
  172. \label Arguments and Values::
  173. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  174. \issue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
  175. \param{result-type}---a \typeref{sequence} \term{type specifier}.
  176. \endissue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
  177. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  178. \issue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
  179. \param{size}---a non-negative \term{integer}.
  180. \endissue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
  181. \param{initial-element}---an \term{object}.
  182. \Default{\term{implementation-dependent}}
  183. \param{sequence}---a \term{proper sequence}.
  184. \label Description::
  185. %% 14.1.0 12
  186. Returns a \term{sequence} of the type \param{result-type} and of length \param{size},
  187. each of the \term{elements} of which has been initialized to \param{initial-element}.
  188. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  189. If the \param{result-type} is a \term{subtype} of \typeref{list},
  190. the result will be a \term{list}.
  191. If the \param{result-type} is a \term{subtype} of \typeref{vector},
  192. then if the implementation can determine the element type specified
  193. for the \param{result-type}, the element type of the resulting array
  194. is the result of \term{upgrading} that element type; or, if the
  195. implementation can determine that the element type is unspecified (or \f{*}),
  196. the element type of the resulting array is \typeref{t};
  197. otherwise, an error is signaled.
  198. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  199. \label Examples::
  200. \code
  201. (make-sequence 'list 0) \EV ()
  202. (make-sequence 'string 26 :initial-element #\\.)
  203. \EV ".........................."
  204. (make-sequence '(vector double-float) 2
  205. :initial-element 1d0)
  206. \EV #(1.0d0 1.0d0)
  207. \endcode
  208. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  209. \code
  210. (make-sequence '(vector * 2) 3) should signal an error
  211. (make-sequence '(vector * 4) 3) should signal an error
  212. \endcode
  213. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  214. \label Affected By::
  215. The \term{implementation}.
  216. \label Exceptional Situations::
  217. The consequences are unspecified if \param{initial-element}
  218. is not an \term{object} which can be stored in the resulting \term{sequence}.
  219. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  220. An error \oftype{type-error} must be signaled if the \param{result-type} is neither
  221. a \term{recognizable subtype} of \typeref{list},
  222. nor a \term{recognizable subtype} of \typeref{vector}.
  223. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  224. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  225. An error \oftype{type-error} should be signaled if \param{result-type} specifies
  226. the number of elements and \param{size} is different from that number.
  227. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  228. \label See Also::
  229. \funref{make-array}, \funref{make-list}
  230. \label Notes::
  231. \issue{CHARACTER-PROPOSAL:2-6-5}
  232. \code
  233. (make-sequence 'string 5) \EQ (make-string 5)
  234. \endcode
  235. \endissue{CHARACTER-PROPOSAL:2-6-5}
  236. \endcom
  237. %%% ========== SUBSEQ
  238. \begincom{subseq}\ftype{Accessor}
  239. %KMP: It's too bad this function is not called subsequence.
  240. \label Syntax::
  241. \DefunWithValues subseq {sequence start {\opt} end} {subsequence}
  242. \Defsetf subseq {sequence start {\opt} end} {new-subsequence}
  243. \label Arguments and Values::
  244. \param{sequence}---a \term{proper sequence}.
  245. \issue{SUBSEQ-OUT-OF-BOUNDS}
  246. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  247. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  248. \DefaultFor{\param{end}}{\nil}
  249. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  250. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  251. \param{subsequence}---a \term{proper sequence}.
  252. \param{new-subsequence}---a \term{proper sequence}.
  253. \label Description::
  254. %% 14.1.0 6
  255. \funref{subseq} creates a \term{sequence}
  256. that is a copy of the subsequence of \param{sequence}
  257. \param{bounded} by \param{start} and \param{end}.
  258. \param{Start} specifies an offset into the original \param{sequence} and
  259. marks the beginning position of the subsequence.
  260. \param{end} marks the position following the last element of the subsequence.
  261. \funref{subseq} always allocates a new \term{sequence} for a result;
  262. it never shares storage with an old \term{sequence}.
  263. The result subsequence is always of the same \term{type} as \param{sequence}.
  264. %% Moon's suggested interpretation follows:
  265. If \param{sequence} is a \term{vector},
  266. the result is a \term{fresh} \term{simple array}
  267. of \term{rank} one
  268. that has the same \term{actual array element type} as \param{sequence}.
  269. If \param{sequence} is a \term{list},
  270. the result is a \term{fresh} \term{list}.
  271. %% End Moon's suggested interpretation.
  272. %% 14.1.0 7
  273. \macref{setf} may be used with \funref{subseq} to destructively replace
  274. \term{elements} of a subsequence with \term{elements}
  275. taken from a \term{sequence} of new values.
  276. If the subsequence and the new sequence are not of equal length,
  277. the shorter length determines the number of elements that are
  278. replaced. The remaining \term{elements} at the end of the longer sequence
  279. are not modified in the operation.
  280. \label Examples::
  281. \code
  282. (setq str "012345") \EV "012345"
  283. (subseq str 2) \EV "2345"
  284. (subseq str 3 5) \EV "34"
  285. (setf (subseq str 4) "abc") \EV "abc"
  286. str \EV "0123ab"
  287. (setf (subseq str 0 2) "A") \EV "A"
  288. str \EV "A123ab"
  289. \endcode
  290. \label Side Effects:\None.
  291. \label Affected By:\None.
  292. \label Exceptional Situations::
  293. \Lazychecktype{sequence}{a \term{proper sequence}}
  294. \Lazychecktype{new-subsequence}{a \term{proper sequence}}
  295. \label See Also::
  296. \funref{replace}
  297. \label Notes:\None.
  298. \endcom
  299. %-------------------- Sequence Mapping --------------------
  300. %%% ========== MAP
  301. \begincom{map}\ftype{Function}
  302. \label Syntax::
  303. \DefunWithValues map {result-type function {\rest} \plus{sequences}} {result}
  304. \label Arguments and Values::
  305. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  306. \param{result-type} -- a \typeref{sequence} \term{type specifier}, or \nil.
  307. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  308. \issue{FUNCTION-TYPE:X3J13-MARCH-88}
  309. \param{function}---a \term{function designator}.
  310. \param{function} must take as many arguments as
  311. there are \param{sequences}.
  312. \endissue{FUNCTION-TYPE:X3J13-MARCH-88}
  313. \param{sequence}---a \term{proper sequence}.
  314. \param{result}---if \param{result-type} is a \term{type specifier} other than \nil,
  315. then a \term{sequence} of the \term{type} it denotes;
  316. otherwise (if the \param{result-type} is \nil), \nil.
  317. \label Description::
  318. %% 7.8.4 3
  319. Applies \param{function} to successive sets of arguments in which
  320. one argument is obtained from each \term{sequence}.
  321. %% 14.2.0 6
  322. The \param{function} is called first on all the elements with index \f{0},
  323. then on all those with index \f{1}, and so on.
  324. The \param{result-type} specifies the \term{type} of the resulting \term{sequence}.
  325. \funref{map} returns \nil\ if \param{result-type} is \nil.
  326. %% 14.2.0 5
  327. Otherwise, \funref{map} returns
  328. a \term{sequence} such that element \f{j} is the result
  329. of applying \param{function} to element \f{j} of each of the
  330. \param{sequences}. The result \term{sequence}
  331. is as long as the shortest of the
  332. \param{sequences}.
  333. The consequences are undefined if the result of applying \param{function}
  334. to the successive elements of the \param{sequences} cannot
  335. be contained in a \term{sequence} of the \term{type} given by \param{result-type}.
  336. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  337. If the \param{result-type} is a \term{subtype} of \typeref{list},
  338. the result will be a \term{list}.
  339. If the \param{result-type} is a \term{subtype} of \typeref{vector},
  340. then if the implementation can determine the element type specified
  341. for the \param{result-type}, the element type of the resulting array
  342. is the result of \term{upgrading} that element type; or, if the
  343. implementation can determine that the element type is unspecified (or \f{*}),
  344. the element type of the resulting array is \typeref{t};
  345. otherwise, an error is signaled.
  346. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  347. \label Examples::
  348. \code
  349. (map 'string #'(lambda (x y)
  350. (char "01234567890ABCDEF" (mod (+ x y) 16)))
  351. '(1 2 3 4)
  352. '(10 9 8 7)) \EV "AAAA"
  353. (setq seq '("lower" "UPPER" "" "123")) \EV ("lower" "UPPER" "" "123")
  354. (map nil #'nstring-upcase seq) \EV NIL
  355. seq \EV ("LOWER" "UPPER" "" "123")
  356. (map 'list #'- '(1 2 3 4)) \EV (-1 -2 -3 -4)
  357. (map 'string
  358. #'(lambda (x) (if (oddp x) #\\1 #\\0))
  359. '(1 2 3 4)) \EV "1010"
  360. \endcode
  361. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  362. \code
  363. (map '(vector * 4) #'cons "abc" "de") should signal an error
  364. \endcode
  365. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  366. \label Affected By:\None.
  367. \label Exceptional Situations::
  368. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  369. An error \oftype{type-error} must be signaled if the \param{result-type} is
  370. not a \term{recognizable subtype} of \typeref{list},
  371. not a \term{recognizable subtype} of \typeref{vector},
  372. and not \nil.
  373. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  374. \Lazycheckanytype{sequence}{a \term{proper sequence}}
  375. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  376. An error \oftype{type-error} should be signaled
  377. if \param{result-type} specifies the
  378. number of elements and the minimum length of the \param{sequences}
  379. is different from that number.
  380. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  381. \label See Also::
  382. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  383. {\secref\TraversalRules}
  384. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  385. \label Notes:\None.
  386. \endcom
  387. %%% ========== MAP-INTO
  388. \begincom{map-into}\ftype{Function}
  389. \issue{MAP-INTO:ADD-FUNCTION}
  390. \label Syntax::
  391. \DefunWithValues map-into {result-sequence function {\rest} sequences} {result-sequence}
  392. \label Arguments and Values::
  393. \param{result-sequence}---a \term{proper sequence}.
  394. \param{function}---a \term{designator} for a \term{function}
  395. of as many \term{arguments} as there are \param{sequences}.
  396. \param{sequence}---a \term{proper sequence}.
  397. \label Description::
  398. Destructively modifies \param{result-sequence} to contain the results of
  399. applying \param{function} to each element in the argument \param{sequences}
  400. in turn.
  401. \param{result-sequence} and each element of \param{sequences} can each be
  402. either a \term{list} or a \term{vector}.
  403. %Note that NIL is considered to be a sequence, of length zero.
  404. If \param{result-sequence} and each element of \param{sequences} are not all
  405. the same length, the iteration terminates when the shortest \term{sequence}
  406. (of any of the \param{sequences} or the \param{result-sequence})
  407. is exhausted.
  408. If \param{result-sequence} is a \term{vector} with a
  409. \term{fill pointer}, the \term{fill pointer} is ignored when deciding how
  410. many iterations to perform, and afterwards the \term{fill pointer} is set to
  411. the number of times \param{function} was applied.
  412. If \param{result-sequence} is longer than the shortest element of \param{sequences},
  413. extra elements at the end of \param{result-sequence} are left unchanged.
  414. If \param{result-sequence} is \nil, \funref{map-into} immediately returns
  415. \nil, since \nil\ is a \term{sequence} of length zero.
  416. If \param{function} has side effects, it can count on being called
  417. first on all of the elements with index 0, then on all of those
  418. numbered 1, and so on.
  419. \label Examples::
  420. \code
  421. (setq a (list 1 2 3 4) b (list 10 10 10 10)) \EV (10 10 10 10)
  422. (map-into a #'+ a b) \EV (11 12 13 14)
  423. a \EV (11 12 13 14)
  424. b \EV (10 10 10 10)
  425. (setq k '(one two three)) \EV (ONE TWO THREE)
  426. (map-into a #'cons k a) \EV ((ONE . 11) (TWO . 12) (THREE . 13) 14)
  427. (map-into a #'gensym) \EV (#:G9090 #:G9091 #:G9092 #:G9093)
  428. a \EV (#:G9090 #:G9091 #:G9092 #:G9093)
  429. \endcode
  430. \label Affected By:\None.
  431. \label Exceptional Situations::
  432. \Lazychecktype{result-sequence}{a \term{proper sequence}}
  433. \Lazychecktype{sequence}{a \term{proper sequence}}
  434. \label See Also:\None.
  435. \label Notes::
  436. \funref{map-into} differs from \funref{map} in that it modifies an
  437. existing \term{sequence} rather than creating a new one.
  438. In addition, \funref{map-into} can be called with only two
  439. arguments, while \funref{map} requires at least three arguments.
  440. %% Barmar supplied this.
  441. \funref{map-into} could be defined by:
  442. \code
  443. (defun map-into (result-sequence function &rest sequences)
  444. (loop for index below (apply #'min
  445. (length result-sequence)
  446. (mapcar #'length sequences))
  447. do (setf (elt result-sequence index)
  448. (apply function
  449. (mapcar #'(lambda (seq) (elt seq index))
  450. sequences))))
  451. result-sequence)
  452. \endcode
  453. \endissue{MAP-INTO:ADD-FUNCTION}
  454. \endcom
  455. %%% ========== REDUCE
  456. \begincom{reduce}\ftype{Function}
  457. \label Syntax::
  458. \DefunWithValues reduce {function sequence {\key} key from-end start end initial-value}
  459. {result}
  460. \label Arguments and Values::
  461. \param{function}---a \term{designator} for a \term{function}
  462. that might be called with either zero or two \term{arguments}.
  463. \param{sequence}---a \term{proper sequence}.
  464. \issue{REDUCE-ARGUMENT-EXTRACTION}
  465. \param{key}---a \term{designator} for a \term{function} of one argument,
  466. or \nil.
  467. \endissue{REDUCE-ARGUMENT-EXTRACTION}
  468. \param{from-end}---a \term{generalized boolean}.
  469. \Default{\term{false}}
  470. \issue{SUBSEQ-OUT-OF-BOUNDS}
  471. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  472. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  473. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  474. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  475. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  476. \param{initial-value}---an \term{object}.
  477. \param{result}---an \term{object}.
  478. \label Description::
  479. %% 14.2.0 17
  480. %% 14.2.0 18
  481. \funref{reduce} uses a binary operation, \param{function},
  482. to combine the \term{elements} of \param{sequence}
  483. \term{bounded} by \param{start} and \param{end}.
  484. The \param{function} must accept as \term{arguments} two \term{elements}
  485. of \param{sequence} or the results from combining those \term{elements}.
  486. The \param{function} must also be able to accept no arguments.
  487. \issue{REDUCE-ARGUMENT-EXTRACTION}
  488. If \param{key} is supplied, it is used is used to extract the values to reduce.
  489. The \param{key} function is applied exactly once to each element of \param{sequence}
  490. in the order implied by the reduction order but not to the value of
  491. \param{initial-value}, if supplied.
  492. \endissue{REDUCE-ARGUMENT-EXTRACTION}
  493. The \param{key} function typically returns part of the \term{element} of \param{sequence}.
  494. If \param{key} is not supplied or is \nil, the \param{sequence} \term{element} itself is used.
  495. The reduction is left-associative,
  496. unless \param{from-end} is \term{true} in which case it is right-associative.
  497. If \param{initial-value} is supplied,
  498. it is logically placed before the subsequence
  499. (or after it if \param{from-end} is \term{true})
  500. and included in the reduction operation.
  501. In the normal case, the result of \funref{reduce} is the combined
  502. result of \param{function}'s being applied to successive pairs of \term{elements}
  503. of \param{sequence}.
  504. %% 14.2.0 19
  505. If the subsequence contains exactly one \term{element}
  506. and no \param{initial-value} is given,
  507. then that \term{element} is returned and \param{function} is not called.
  508. If the subsequence is empty and an \param{initial-value} is given,
  509. then the \param{initial-value} is returned and \param{function} is not called.
  510. %% 14.2.0 20
  511. If the subsequence is empty and no \param{initial-value} is given,
  512. then the \param{function} is called with zero arguments,
  513. and \funref{reduce} returns whatever \param{function} does.
  514. This is the only case where the
  515. \param{function} is called with other than two arguments.
  516. \label Examples::
  517. %% 14.2.0 21
  518. \code
  519. (reduce #'* '(1 2 3 4 5)) \EV 120
  520. (reduce #'append '((1) (2)) :initial-value '(i n i t)) \EV (I N I T 1 2)
  521. (reduce #'append '((1) (2)) :from-end t
  522. :initial-value '(i n i t)) \EV (1 2 I N I T)
  523. (reduce #'- '(1 2 3 4)) \EQ (- (- (- 1 2) 3) 4) \EV -8
  524. (reduce #'- '(1 2 3 4) :from-end t) ;Alternating sum.
  525. \EQ (- 1 (- 2 (- 3 4))) \EV -2
  526. (reduce #'+ '()) \EV 0
  527. (reduce #'+ '(3)) \EV 3
  528. (reduce #'+ '(foo)) \EV FOO
  529. (reduce #'list '(1 2 3 4)) \EV (((1 2) 3) 4)
  530. (reduce #'list '(1 2 3 4) :from-end t) \EV (1 (2 (3 4)))
  531. (reduce #'list '(1 2 3 4) :initial-value 'foo) \EV ((((foo 1) 2) 3) 4)
  532. (reduce #'list '(1 2 3 4)
  533. :from-end t :initial-value 'foo) \EV (1 (2 (3 (4 foo))))
  534. \endcode
  535. \label Side Effects:\None.
  536. \label Affected By:\None.
  537. \label Exceptional Situations::
  538. \Lazychecktype{sequence}{a \term{proper sequence}}
  539. \label See Also::
  540. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  541. {\secref\TraversalRules}
  542. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  543. \label Notes:\None.
  544. \endcom
  545. %-------------------- Sequence Counting --------------------
  546. %%% ========== COUNT
  547. %%% ========== COUNT-IF
  548. %%% ========== COUNT-IF-NOT
  549. \begincom{count, count-if, count-if-not}\ftype{Function}
  550. \label Syntax::
  551. \DefunWithValues count {item sequence {\key} from-end start end key test test-not} {n}
  552. \DefunWithValues count-if {predicate sequence {\key} from-end start end key} {n}
  553. \DefunWithValues count-if-not {predicate sequence {\key} from-end start end key} {n}
  554. \label Arguments and Values::
  555. \param{item}---an \term{object}.
  556. \param{sequence}---a \term{proper sequence}.
  557. \param{predicate}---a \term{designator} for a \term{function} of one \term{argument}
  558. that returns a \term{generalized boolean}.
  559. \param{from-end}---a \term{generalized boolean}.
  560. \Default{\term{false}}
  561. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  562. that returns a \term{generalized boolean}.
  563. \param{test-not}---a \term{designator} for
  564. a \term{function} of two \term{arguments}
  565. that returns a \term{generalized boolean}.
  566. \issue{SUBSEQ-OUT-OF-BOUNDS}
  567. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  568. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  569. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  570. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  571. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  572. \param{key}---a \term{designator} for a \term{function} of one argument,
  573. or \nil.
  574. \param{n}---a non-negative \term{integer}
  575. less than or equal to the \term{length} of \param{sequence}.
  576. \label Description::
  577. %% 14.3.0 32
  578. \funref{count}, \funref{count-if}, and \funref{count-if-not}
  579. count and return the number of \term{elements} in
  580. the \param{sequence} \term{bounded} by \param{start} and \param{end}
  581. that \term{satisfy the test}.
  582. The \param{from-end} has no direct effect on the result.
  583. However, if \param{from-end} is \term{true},
  584. the \term{elements} of \param{sequence} will be supplied as \term{arguments} to
  585. the \param{test},
  586. \param{test-not},
  587. and \param{key} in reverse order,
  588. which may change the side-effects, if any, of those functions.
  589. \label Examples::
  590. \code
  591. (count #\\a "how many A's are there in here?") \EV 2
  592. (count-if-not #'oddp '((1) (2) (3) (4)) :key #'car) \EV 2
  593. (count-if #'upper-case-p "The Crying of Lot 49" :start 4) \EV 2
  594. \endcode
  595. \label Side Effects:\None.
  596. \label Affected By:\None.
  597. \label Exceptional Situations::
  598. \Lazychecktype{sequence}{a \term{proper sequence}}
  599. \label See Also::
  600. {\secref\TestFunctionRules},
  601. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  602. {\secref\TraversalRules}
  603. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  604. \label Notes::
  605. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  606. The \kwd{test-not} \term{argument} is deprecated.
  607. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  608. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  609. \Thefunction{count-if-not} is deprecated.
  610. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  611. \endcom
  612. %%% ========== LENGTH
  613. \begincom{length}\ftype{Function}
  614. \label Syntax::
  615. \DefunWithValues length {sequence} {n}
  616. \label Arguments and Values::
  617. \param{sequence}---a \term{proper sequence}.
  618. \param{n}---a non-negative \term{integer}.
  619. \label Description::
  620. %% 14.1.0 9
  621. Returns the number of \term{elements} in \param{sequence}.
  622. If \param{sequence} is a \term{vector} with a \term{fill pointer},
  623. the active length as specified by the \term{fill pointer} is returned.
  624. \label Examples::
  625. \code
  626. (length "abc") \EV 3
  627. (setq str (make-array '(3) :element-type 'character
  628. :initial-contents "abc"
  629. :fill-pointer t)) \EV "abc"
  630. (length str) \EV 3
  631. (setf (fill-pointer str) 2) \EV 2
  632. (length str) \EV 2
  633. \endcode
  634. \label Affected By:\None.
  635. \label Exceptional Situations::
  636. \Lazychecktype{sequence}{a \term{proper sequence}}
  637. %%It's implied by lazychecktype.
  638. %The results are undefined if \param{sequence} is a \term{circular list}.
  639. \label See Also::
  640. \funref{list-length},
  641. \typeref{sequence}
  642. %% Per X3J13. -kmp 05-Oct-93
  643. \label Notes:\None.
  644. \endcom
  645. %-------------------- Sequence Ordering --------------------
  646. %%% ========== REVERSE
  647. %%% ========== NREVERSE
  648. \begincom{reverse, nreverse}\ftype{Function}
  649. \label Syntax::
  650. \DefunWithValues reverse {sequence} {reversed-sequence}
  651. \DefunWithValues nreverse {sequence} {reversed-sequence}
  652. \label Arguments and Values::
  653. \param{sequence}---a \term{proper sequence}.
  654. %% 14.1.0 10
  655. \param{reversed-sequence}---a \term{sequence}.
  656. \label Description::
  657. \funref{reverse} and \funref{nreverse} return a new \term{sequence}
  658. of the same kind as \param{sequence}, containing the same \term{elements},
  659. but in reverse order.
  660. \funref{reverse} and \funref{nreverse} differ in that \funref{reverse}
  661. always creates and returns a new \term{sequence}, whereas \funref{nreverse}
  662. might modify and return the given \param{sequence}. \funref{reverse} never
  663. modifies the given \param{sequence}.
  664. %% Moon's suggested interpretation follows:
  665. For \funref{reverse}, if \param{sequence} is a \term{vector},
  666. the result is a \term{fresh} \term{simple array} of \term{rank} one
  667. that has the same \term{actual array element type} as \param{sequence}.
  668. If \param{sequence} is a \term{list}, the result is a \term{fresh} \term{list}.
  669. For \funref{nreverse}, if \param{sequence} is a \term{vector},
  670. the result is a \term{vector}
  671. that has the same \term{actual array element type} as \param{sequence}.
  672. If \param{sequence} is a \term{list}, the result is a \term{list}.
  673. %% End Moon's suggested interpretation.
  674. %% 14.1.0 11
  675. For \funref{nreverse},
  676. \param{sequence} might be destroyed and re-used to produce the result.
  677. The result might or might not be \term{identical} to \param{sequence}.
  678. \issue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  679. Specifically, when \param{sequence} is a \term{list},
  680. \funref{nreverse} is permitted to \macref{setf} any part, \funref{car} or \funref{cdr},
  681. of any \term{cons} that is part of the \term{list structure} of \param{sequence}.
  682. When \param{sequence} is a \term{vector},
  683. \funref{nreverse} is permitted to re-order the elements of \param{sequence}
  684. in order to produce the resulting \term{vector}.
  685. \endissue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  686. \label Examples::
  687. \code
  688. (setq str "abc") \EV "abc"
  689. (reverse str) \EV "cba"
  690. str \EV "abc"
  691. (setq str (copy-seq str)) \EV "abc"
  692. (nreverse str) \EV "cba"
  693. str \EV \term{implementation-dependent}
  694. (setq l (list 1 2 3)) \EV (1 2 3)
  695. (nreverse l) \EV (3 2 1)
  696. l \EV \term{implementation-dependent}
  697. \endcode
  698. \label Side Effects::
  699. \funref{nreverse} might either create a new \term{sequence},
  700. modify the argument \param{sequence}, or both.
  701. %\funref{reverse} returns a \term{potential copy} of \param{sequence}.
  702. (\funref{reverse} does not modify \param{sequence}.)
  703. \label Affected By:\None.
  704. \label Exceptional Situations::
  705. \Lazychecktype{sequence}{a \term{proper sequence}}
  706. \label See Also:\None.
  707. \label Notes:\None.
  708. \endcom
  709. %%% ========== SORT
  710. %%% ========== STABLE-SORT
  711. \begincom{sort, stable-sort}\ftype{Function}
  712. \label Syntax::
  713. \DefunWithValues sort {sequence predicate {\key} key} {sorted-sequence}
  714. \DefunWithValues stable-sort {sequence predicate {\key} key} {sorted-sequence}
  715. \label Arguments and Values::
  716. \param{sequence}---a \term{proper sequence}.
  717. \param{predicate}---a \term{designator} for
  718. a \term{function} of two arguments that returns a \term{generalized boolean}.
  719. %% 14.4.0 4
  720. \param{key}---a \term{designator} for a \term{function} of one argument,
  721. or \nil.
  722. \param{sorted-sequence}---a \term{sequence}.
  723. \label Description::
  724. %% 14.4.0 2
  725. \funref{sort} and \funref{stable-sort} destructively sort \param{sequences}
  726. according to the order determined by the \param{predicate} function.
  727. %% Moon's suggested interpretation follows:
  728. If \param{sequence} is a \term{vector},
  729. the result is a \term{vector}
  730. that has the same \term{actual array element type} as \param{sequence}.
  731. %% Moved to notes per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  732. %% -kmp 9-May-94
  733. % The result might or might not be simple,
  734. % and might or might not be \term{identical} to \param{sequence}.
  735. %% Another possible interpretation:
  736. %% The result might or might not be \term{identical} to \param{sequence}.
  737. %% If the result is a \term{vector} that is not \term{identical}
  738. %% to \param{sequence}, the result is a \term{fresh} \term{simple array}
  739. %% of \term{rank} one.
  740. If \param{sequence} is a \term{list},
  741. the result is a \term{list}.
  742. %% End Moon's suggested interpretation.
  743. %% 14.4.0 3
  744. \funref{sort} determines the relationship between two elements
  745. by giving keys extracted from the elements to the \param{predicate}.
  746. The first argument to the \param{predicate} function is the part of one element
  747. of \param{sequence} extracted by the \param{key} function
  748. (if supplied); the second
  749. argument is the part of another element
  750. of \param{sequence} extracted by the \param{key} function
  751. (if supplied).
  752. \param{Predicate} should return \term{true} if and only if the first argument is
  753. strictly less than the second (in some appropriate sense).
  754. If the first argument is greater than or equal to the second
  755. (in the appropriate sense), then the \param{predicate} should return \term{false}.
  756. The argument to the \param{key} function is the \param{sequence} element.
  757. The return value of the \param{key} function
  758. becomes an argument to \param{predicate}.
  759. If \param{key} is not supplied or \nil, the \param{sequence} element itself is used.
  760. There is no guarantee on the number of times the \param{key} will be called.
  761. %% 14.4.0 5
  762. If the \param{key} and \param{predicate} always return,
  763. then the sorting operation will always terminate,
  764. producing a \term{sequence} containing the same \term{elements} as \param{sequence}
  765. (that is, the result is a permutation of \param{sequence}).
  766. This is guaranteed even if the \param{predicate}
  767. does not really consistently represent a total order
  768. (in which case the \term{elements} will be scrambled in some unpredictable way,
  769. but no \term{element} will be lost).
  770. If the \param{key} consistently returns meaningful keys,
  771. and the \param{predicate} does reflect some total ordering criterion on those keys,
  772. then the \term{elements} of the \param{sorted-sequence}
  773. will be properly sorted according to that ordering.
  774. %% 14.4.0 6
  775. The sorting operation performed by \funref{sort} is not guaranteed stable.
  776. Elements considered equal by the \param{predicate} might or might not
  777. stay in their original order. The \param{predicate} is assumed to
  778. consider two elements \f{x} and \f{y} to be equal if
  779. \f{(funcall \i{predicate} \i{x} \i{y})} and
  780. \f{(funcall \i{predicate} \i{y} \i{x})} are both \term{false}.
  781. \funref{stable-sort} guarantees stability.
  782. %% 14.5.0 7
  783. The sorting operation can be destructive in all cases. In the case of a
  784. \term{vector}
  785. argument, this is accomplished by permuting the elements in place.
  786. In the case of a \term{list}, the \term{list} is
  787. destructively reordered in the same manner as for
  788. \funref{nreverse}.
  789. %% 14.4.0 9
  790. %% this paragraph left out
  791. \label Examples::
  792. \code
  793. (setq tester (copy-seq "lkjashd")) \EV "lkjashd"
  794. (sort tester #'char-lessp) \EV "adhjkls"
  795. (setq tester (list '(1 2 3) '(4 5 6) '(7 8 9))) \EV ((1 2 3) (4 5 6) (7 8 9))
  796. (sort tester #'> :key #'car) \EV ((7 8 9) (4 5 6) (1 2 3))
  797. (setq tester (list 1 2 3 4 5 6 7 8 9 0)) \EV (1 2 3 4 5 6 7 8 9 0)
  798. (stable-sort tester #'(lambda (x y) (and (oddp x) (evenp y))))
  799. \EV (1 3 5 7 9 2 4 6 8 0)
  800. (sort (setq committee-data
  801. (vector (list (list "JonL" "White") "Iteration")
  802. (list (list "Dick" "Waters") "Iteration")
  803. (list (list "Dick" "Gabriel") "Objects")
  804. (list (list "Kent" "Pitman") "Conditions")
  805. (list (list "Gregor" "Kiczales") "Objects")
  806. (list (list "David" "Moon") "Objects")
  807. (list (list "Kathy" "Chapman") "Editorial")
  808. (list (list "Larry" "Masinter") "Cleanup")
  809. (list (list "Sandra" "Loosemore") "Compiler")))
  810. #'string-lessp :key #'cadar)
  811. \EV #((("Kathy" "Chapman") "Editorial")
  812. (("Dick" "Gabriel") "Objects")
  813. (("Gregor" "Kiczales") "Objects")
  814. (("Sandra" "Loosemore") "Compiler")
  815. (("Larry" "Masinter") "Cleanup")
  816. (("David" "Moon") "Objects")
  817. (("Kent" "Pitman") "Conditions")
  818. (("Dick" "Waters") "Iteration")
  819. (("JonL" "White") "Iteration"))
  820. ;; Note that individual alphabetical order within `committees'
  821. ;; is preserved.
  822. (setq committee-data
  823. (stable-sort committee-data #'string-lessp :key #'cadr))
  824. \EV #((("Larry" "Masinter") "Cleanup")
  825. (("Sandra" "Loosemore") "Compiler")
  826. (("Kent" "Pitman") "Conditions")
  827. (("Kathy" "Chapman") "Editorial")
  828. (("Dick" "Waters") "Iteration")
  829. (("JonL" "White") "Iteration")
  830. (("Dick" "Gabriel") "Objects")
  831. (("Gregor" "Kiczales") "Objects")
  832. (("David" "Moon") "Objects"))
  833. \endcode
  834. \label Side Effects:\None.
  835. \label Affected By:\None.
  836. \label Exceptional Situations::
  837. \Lazychecktype{sequence}{a \term{proper sequence}}
  838. \label See Also::
  839. \funref{merge},
  840. \issue{CONSTANT-MODIFICATION:DISALLOW}
  841. {\secref\ConstantModification},
  842. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  843. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  844. {\secref\TraversalRules},
  845. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  846. {\secref\DestructiveOperations}
  847. \label Notes::
  848. %% Moved from Description per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  849. %% -kmp 9-May-94
  850. If \param{sequence} is a \term{vector},
  851. the result might or might not be simple,
  852. and might or might not be \term{identical} to \param{sequence}.
  853. \endcom
  854. %-------------------- Sequence Search --------------------
  855. %%% ========== FIND
  856. %%% ========== FIND-IF
  857. %%% ========== FIND-IF-NOT
  858. \begincom{find, find-if, find-if-not}\ftype{Function}
  859. \label Syntax::
  860. \DefunWithValues find {item sequence {\key} from-end test test-not start end key} {element}
  861. \DefunWithValues find-if {predicate sequence {\key} from-end start end key} {element}
  862. \DefunWithValues find-if-not {predicate sequence {\key} from-end start end key} {element}
  863. \label Arguments and Values::
  864. \param{item}---an \term{object}.
  865. \param{sequence}---a \term{proper sequence}.
  866. \param{predicate}---a \term{designator} for a \term{function} of one \term{argument}
  867. that returns a \term{generalized boolean}.
  868. \param{from-end}---a \term{generalized boolean}.
  869. \Default{\term{false}}
  870. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  871. that returns a \term{generalized boolean}.
  872. \param{test-not}---a \term{designator} for
  873. a \term{function} of two \term{arguments}
  874. that returns a \term{generalized boolean}.
  875. \issue{SUBSEQ-OUT-OF-BOUNDS}
  876. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  877. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  878. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  879. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  880. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  881. \param{key}---a \term{designator} for a \term{function} of one argument,
  882. or \nil.
  883. \param{element}---an \term{element} of the \param{sequence}, or \nil.
  884. \label Description::
  885. \funref{find}, \funref{find-if}, and \funref{find-if-not}
  886. each search for an \term{element} of the \param{sequence}
  887. \term{bounded} by \param{start} and \term{end}
  888. that \term{satisfies the predicate} \param{predicate}
  889. or that \term{satisfies the test} \param{test} or \param{test-not},
  890. as appropriate.
  891. %% 14.3.0 28
  892. If \param{from-end} is \term{true},
  893. then the result is the rightmost \term{element} that \term{satisfies the test}.
  894. %% 14.3.0 26
  895. If the \param{sequence} contains an \term{element} that \term{satisfies the test},
  896. then the leftmost or rightmost \param{sequence} element,
  897. depending on \param{from-end},
  898. is returned;
  899. otherwise \nil\ is returned.
  900. \label Examples::
  901. \code
  902. (find #\\d "here are some letters that can be looked at" :test #'char>)
  903. \EV #\\Space
  904. (find-if #'oddp '(1 2 3 4 5) :end 3 :from-end t) \EV 3
  905. (find-if-not #'complexp
  906. '#(3.5 2 #C(1.0 0.0) #C(0.0 1.0))
  907. :start 2) \EV NIL
  908. \endcode
  909. \label Side Effects:\None.
  910. \label Affected By:\None.
  911. \label Exceptional Situations::
  912. \Lazychecktype{sequence}{a \term{proper sequence}}
  913. \label See Also::
  914. \funref{position},
  915. {\secref\TestFunctionRules},
  916. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  917. {\secref\TraversalRules}
  918. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  919. \label Notes::
  920. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  921. The \kwd{test-not} \term{argument} is deprecated.
  922. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  923. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  924. \Thefunction{find-if-not} is deprecated.
  925. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  926. %% This equivalence isn't true when the element isn't found. -kmp 14-Jan-91
  927. %
  928. % \code
  929. % (find item sequence ...)
  930. % \EQ (elt sequence (position item sequence ...))
  931. % \endcode
  932. \endcom
  933. %%% ========== POSITION
  934. %%% ========== POSITION-IF
  935. %%% ========== POSITION-IF-NOT
  936. \begincom{position, position-if, position-if-not}\ftype{Function}
  937. \label Syntax::
  938. \DefunWithValues position
  939. {item sequence {\key} from-end test test-not start end key}
  940. {position}
  941. \DefunWithValues position-if {predicate sequence {\key} from-end start end key} {position}
  942. \DefunWithValues position-if-not {predicate sequence {\key} from-end start end key} {position}
  943. \label Arguments and Values::
  944. \param{item}---an \term{object}.
  945. \param{sequence}---a \term{proper sequence}.
  946. \param{predicate}---a \term{designator} for a \term{function} of one argument
  947. that returns a \term{generalized boolean}.
  948. \param{from-end}---a \term{generalized boolean}.
  949. \Default{\term{false}}
  950. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  951. that returns a \term{generalized boolean}.
  952. \param{test-not}---a \term{designator} for
  953. a \term{function} of two \term{arguments}
  954. that returns a \term{generalized boolean}.
  955. \issue{SUBSEQ-OUT-OF-BOUNDS}
  956. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  957. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  958. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  959. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  960. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  961. \param{key}---a \term{designator} for a \term{function} of one argument,
  962. or \nil.
  963. \param{position}---a \term{bounding index} of \param{sequence}, or \nil.
  964. \label Description::
  965. \funref{position}, \funref{position-if}, and \funref{position-if-not}
  966. each search \param{sequence} for an \term{element} that \term{satisfies the test}.
  967. %% 14.3.0 29
  968. %% 14.3.0 31
  969. The \param{position} returned is the index within \param{sequence}
  970. of the leftmost (if \param{from-end} is \term{true})
  971. or of the rightmost (if \param{from-end} is \term{false})
  972. \term{element} that \term{satisfies the test};
  973. otherwise \nil\ is returned.
  974. %% 14.3.0 30
  975. The index returned is relative to the left-hand end of the entire \param{sequence},
  976. regardless of the value of \term{start}, \term{end}, or \term{from-end}.
  977. \label Examples::
  978. \code
  979. (position #\\a "baobab" :from-end t) \EV 4
  980. (position-if #'oddp '((1) (2) (3) (4)) :start 1 :key #'car) \EV 2
  981. (position 595 '()) \EV NIL
  982. (position-if-not #'integerp '(1 2 3 4 5.0)) \EV 4
  983. \endcode
  984. \label Side Effects:\None.
  985. \label Affected By:\None.
  986. \label Exceptional Situations::
  987. \Lazychecktype{sequence}{a \term{proper sequence}}
  988. \label See Also::
  989. \funref{find},
  990. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  991. {\secref\TraversalRules}
  992. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  993. \label Notes::
  994. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  995. The \kwd{test-not} \term{argument} is deprecated.
  996. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  997. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  998. \Thefunction{position-if-not} is deprecated.
  999. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1000. \endcom
  1001. %%% ========== SEARCH
  1002. \begincom{search}\ftype{Function}
  1003. \label Syntax::
  1004. \DefunWithValuesNewline search
  1005. {sequence-1 sequence-2
  1006. {\key} \vtop{\hbox{from-end test test-not}
  1007. \hbox{key start1 start2}
  1008. \hbox{end1 end2}}}
  1009. {position}
  1010. \label Arguments and Values::
  1011. \param{Sequence-1}---a \term{sequence}.
  1012. \param{Sequence-2}---a \term{sequence}.
  1013. \param{from-end}---a \term{generalized boolean}.
  1014. \Default{\term{false}}
  1015. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  1016. that returns a \term{generalized boolean}.
  1017. \param{test-not}---a \term{designator} for
  1018. a \term{function} of two \term{arguments}
  1019. that returns a \term{generalized boolean}.
  1020. \param{key}---a \term{designator} for a \term{function} of one argument,
  1021. or \nil.
  1022. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1023. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1024. \param{start1}, \param{end1}---\term{bounding index designators} of \param{sequence-1}.
  1025. \Defaults{\param{start1} and \param{end1}}{\f{0} and \nil}
  1026. \param{start2}, \param{end2}---\term{bounding index designators} of \param{sequence-2}.
  1027. \Defaults{\param{start2} and \param{end2}}{\f{0} and \nil}
  1028. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1029. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1030. \param{position}---a \term{bounding index} of \param{sequence-2},
  1031. or \nil.
  1032. \label Description::
  1033. %% 14.3.0 36
  1034. Searches \param{sequence-2} for a subsequence that matches \param{sequence-1}.
  1035. %% 14.3.0 38
  1036. The implementation may choose to search \param{sequence-2} in any order;
  1037. there is no guarantee on the number of times the test is made.
  1038. For example,
  1039. when \param{start-end} is \term{true},
  1040. the \param{sequence} might actually be searched from left to right
  1041. instead of from right to left (but in either case would return
  1042. the rightmost matching subsequence).
  1043. If the search succeeds,
  1044. \funref{search} returns the offset into \param{sequence-2}
  1045. of the first element of the leftmost or rightmost matching subsequence,
  1046. depending on \param{from-end};
  1047. otherwise \funref{search} returns \nil.
  1048. %% 14.3.0 37
  1049. If \param{from-end} is \term{true}, the index of the leftmost
  1050. element of the rightmost matching subsequence is returned.
  1051. \label Examples::
  1052. \code
  1053. (search "dog" "it's a dog's life") \EV 7
  1054. (search '(0 1) '(2 4 6 1 3 5) :key #'oddp) \EV 2
  1055. \endcode
  1056. \label Side Effects:\None.
  1057. \label Affected By:\None.
  1058. \label Exceptional Situations:\None.
  1059. \label See Also::
  1060. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1061. {\secref\TraversalRules}
  1062. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1063. \label Notes::
  1064. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1065. The \kwd{test-not} \term{argument} is deprecated.
  1066. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1067. \endcom
  1068. %-------------------- Sequence Comparison --------------------
  1069. %%% ========== MISMATCH
  1070. \begincom{mismatch}\ftype{Function}
  1071. \label Syntax::
  1072. \DefunWithValuesNewline mismatch
  1073. {sequence-1 sequence-2
  1074. {\key} from-end test test-not key start1 start2 end1 end2}
  1075. {position}
  1076. \label Arguments and Values::
  1077. \param{Sequence-1}---a \term{sequence}.
  1078. \param{Sequence-2}---a \term{sequence}.
  1079. \param{from-end}---a \term{generalized boolean}.
  1080. \Default{\term{false}}
  1081. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  1082. that returns a \term{generalized boolean}.
  1083. \param{test-not}---a \term{designator} for
  1084. a \term{function} of two \term{arguments}
  1085. that returns a \term{generalized boolean}.
  1086. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1087. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1088. \param{start1}, \param{end1}---\term{bounding index designators} of \param{sequence-1}.
  1089. \Defaults{\param{start1} and \param{end1}}{\f{0} and \nil}
  1090. \param{start2}, \param{end2}---\term{bounding index designators} of \param{sequence-2}.
  1091. \Defaults{\param{start2} and \param{end2}}{\f{0} and \nil}
  1092. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1093. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1094. \param{key}---a \term{designator} for a \term{function} of one argument,
  1095. or \nil.
  1096. \param{position}---a \term{bounding index} of \param{sequence-1},
  1097. or \nil.
  1098. \label Description::
  1099. %% 14.3.0 34
  1100. The specified subsequences of
  1101. \param{sequence-1} and \param{sequence-2} are compared element-wise.
  1102. The \param{key} argument is used for both the \param{sequence-1} and the \param{sequence-2}.
  1103. If \param{sequence-1} and \param{sequence-2}
  1104. are of equal length and match in every element, the result is
  1105. \term{false}. Otherwise, the result is a non-negative \term{integer},
  1106. the index within
  1107. \param{sequence-1} of the leftmost or rightmost position, depending
  1108. on \param{from-end}, at which the two
  1109. subsequences fail to match.
  1110. If one subsequence
  1111. is shorter than and a matching prefix of the other,
  1112. the result is the index
  1113. relative to \param{sequence-1} beyond the last position tested.
  1114. %% 14.3.0 35
  1115. If \param{from-end} is \term{true}, then one plus the index of the rightmost
  1116. position in which the \param{sequences}
  1117. differ is returned. In effect, the subsequences
  1118. are aligned at their right-hand ends; then, the last elements are compared,
  1119. the penultimate elements, and so on. The index returned is
  1120. an index relative to \param{sequence-1}.
  1121. \label Examples::
  1122. \code
  1123. (mismatch "abcd" "ABCDE" :test #'char-equal) \EV 4
  1124. (mismatch '(3 2 1 1 2 3) '(1 2 3) :from-end t) \EV 3
  1125. (mismatch '(1 2 3) '(2 3 4) :test-not #'eq :key #'oddp) \EV NIL
  1126. (mismatch '(1 2 3 4 5 6) '(3 4 5 6 7) :start1 2 :end2 4) \EV NIL
  1127. \endcode
  1128. \label Side Effects:\None.
  1129. \label Affected By:\None.
  1130. \label Exceptional Situations:\None.
  1131. \label See Also::
  1132. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1133. {\secref\TraversalRules}
  1134. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1135. \label Notes::
  1136. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1137. The \kwd{test-not} \term{argument} is deprecated.
  1138. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1139. \endcom
  1140. %-------------------- Sequence Substitution --------------------
  1141. %%% ========== REPLACE
  1142. \begincom{replace}\ftype{Function}
  1143. \label Syntax::
  1144. \DefunWithValues replace
  1145. {sequence-1 sequence-2 {\key} start1 end1 start2 end2}
  1146. {sequence-1}
  1147. \label Arguments and Values::
  1148. \param{sequence-1}---a \term{sequence}.
  1149. \param{sequence-2}---a \term{sequence}.
  1150. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1151. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1152. \param{start1}, \param{end1}---\term{bounding index designators} of \param{sequence-1}.
  1153. \Defaults{\param{start1} and \param{end1}}{\f{0} and \nil}
  1154. \param{start2}, \param{end2}---\term{bounding index designators} of \param{sequence-2}.
  1155. \Defaults{\param{start2} and \param{end2}}{\f{0} and \nil}
  1156. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1157. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1158. \label Description::
  1159. Destructively modifies \param{sequence-1}
  1160. by replacing the \term{elements} of \param{subsequence-1}
  1161. \term{bounded} by \param{start1} and \param{end1}
  1162. with the \term{elements} of \param{subsequence-2}
  1163. \term{bounded} by \param{start2} and \param{end2}.
  1164. %% 14.3.0 4
  1165. \param{Sequence-1} is destructively modified by copying successive
  1166. \term{elements} into it from \param{sequence-2}.
  1167. \term{Elements} of the subsequence of \param{sequence-2}
  1168. \term{bounded} by \param{start2} and \param{end2}
  1169. are copied into the subsequence of \param{sequence-1}
  1170. \term{bounded} by \param{start1} and \param{end1}.
  1171. If these subsequences are not of the same length,
  1172. then the shorter length determines how many \term{elements} are copied;
  1173. the extra \term{elements} near the end of the longer subsequence
  1174. are not involved in the operation.
  1175. The number of elements copied can be expressed as:
  1176. \code
  1177. (min (- \i{end1} \i{start1}) (- \i{end2} \i{start2}))
  1178. \endcode
  1179. %% 14.3.0 5
  1180. If \param{sequence-1} and \param{sequence-2} are the \term{same} \term{object}
  1181. and the region being modified overlaps the region being copied
  1182. from, then it is as if the entire source region were copied to another
  1183. place and only then copied back into the target region.
  1184. However, if \param{sequence-1} and \param{sequence-2} are not the same,
  1185. but the region being modified overlaps the region being copied from
  1186. (perhaps because of shared list structure or displaced \term{arrays}),
  1187. then after the \funref{replace} operation
  1188. the subsequence of \param{sequence-1} being modified will have
  1189. unpredictable contents.
  1190. It is an error if the elements of \param{sequence-2} are not of a
  1191. \term{type} that can be stored into \param{sequence-1}.
  1192. \label Examples::
  1193. \code
  1194. (replace "abcdefghij" "0123456789" :start1 4 :end1 7 :start2 4)
  1195. \EV "abcd456hij"
  1196. (setq lst "012345678") \EV "012345678"
  1197. (replace lst lst :start1 2 :start2 0) \EV "010123456"
  1198. lst \EV "010123456"
  1199. \endcode
  1200. \label Side Effects::
  1201. The \param{sequence-1} is modified.
  1202. \label Affected By:\None.
  1203. \label Exceptional Situations:\None.
  1204. \label See Also::
  1205. \funref{fill}
  1206. %% Per X3J13. -kmp 05-Oct-93
  1207. \label Notes:\None.
  1208. \endcom
  1209. %%% ========== SUBSTITUTE
  1210. %%% ========== SUBSTITUTE-IF
  1211. %%% ========== SUBSTITUTE-IF-NOT
  1212. %%% ========== NSUBSTITUTE
  1213. %%% ========== NSUBSTITUTE-IF
  1214. %%% ========== NSUBSTITUTE-IF-NOT
  1215. \begincom{substitute, substitute-if, substitute-if-not,
  1216. nsubstitute, nsubstitute-if, nsubstitute-if-not}\ftype{Function}
  1217. \label Syntax::
  1218. \DefunWithValuesNewline substitute
  1219. {newitem olditem sequence
  1220. {\key} \vtop{\hbox{from-end test}
  1221. \hbox{test-not start}
  1222. \hbox{end count key}}}
  1223. {result-sequence}
  1224. \DefunWithValuesNewline substitute-if
  1225. {newitem predicate sequence {\key} from-end start end count key}
  1226. {result-sequence}
  1227. \DefunWithValuesNewline substitute-if-not
  1228. {newitem predicate sequence {\key} from-end start end count key}
  1229. {result-sequence}
  1230. \DefunWithValuesNewline nsubstitute
  1231. {newitem olditem sequence
  1232. {\key} from-end test test-not start end count key}
  1233. {sequence}
  1234. \DefunWithValuesNewline nsubstitute-if
  1235. {newitem predicate sequence {\key} from-end start end count key}
  1236. {sequence}
  1237. \DefunWithValuesNewline nsubstitute-if-not
  1238. {newitem predicate sequence {\key} from-end start end count key}
  1239. {sequence}
  1240. \label Arguments and Values::
  1241. \param{newitem}---an \term{object}.
  1242. \param{olditem}---an \term{object}.
  1243. \param{sequence}---a \term{proper sequence}.
  1244. \param{predicate}---a \term{designator} for a \term{function} of one \term{argument}
  1245. that returns a \term{generalized boolean}.
  1246. \param{from-end}---a \term{generalized boolean}.
  1247. \Default{\term{false}}
  1248. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  1249. that returns a \term{generalized boolean}.
  1250. \param{test-not}---a \term{designator} for
  1251. a \term{function} of two \term{arguments}
  1252. that returns a \term{generalized boolean}.
  1253. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1254. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1255. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  1256. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  1257. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1258. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1259. \issue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1260. \param{count}---an \term{integer} or \nil.
  1261. \endissue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1262. \Default{\nil}
  1263. \param{key}---a \term{designator} for a \term{function} of one argument,
  1264. or \nil.
  1265. \param{result-sequence}---a \term{sequence}.
  1266. \label Description::
  1267. \funref{substitute}, \funref{substitute-if}, and \funref{substitute-if-not}
  1268. return a
  1269. %% Sandra is queasy about this.
  1270. % modified
  1271. copy of \param{sequence} in which each \term{element}
  1272. that \term{satisfies the test} has been replaced with \param{newitem}.
  1273. \funref{nsubstitute}, \funref{nsubstitute-if}, and \funref{nsubstitute-if-not}
  1274. are like \funref{substitute}, \funref{substitute-if}, and
  1275. \funref{substitute-if-not} respectively, but they may modify
  1276. \param{sequence}.
  1277. %% Moon's suggested interpretation follows:
  1278. If
  1279. \param{sequence} is a \term{vector}, the result is a
  1280. \term{vector} that has the same
  1281. \term{actual array element type} as \param{sequence}.
  1282. %% Moved to notes per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1283. %% -kmp 9-May-94
  1284. % The result might or might not be simple,
  1285. % and might or might not be \term{identical} to \param{sequence}.
  1286. %% Another possible interpretation:
  1287. %% The result might or might not be \term{identical} to \param{sequence}.
  1288. %% If the result is a \term{vector} that is not \term{identical}
  1289. %% to \param{sequence}, the result is a \term{fresh} \term{simple array}
  1290. %% of \term{rank} one.
  1291. If \param{sequence} is a \term{list}, the result is a
  1292. \term{list}.
  1293. %% End Moon's suggested interpretation.
  1294. %% 14.3.0 20
  1295. \param{Count}, if supplied, limits the number of elements
  1296. altered; if more than \param{count} \term{elements} \term{satisfy the test},
  1297. then of these \term{elements} only the leftmost or rightmost, depending
  1298. on \param{from-end}, are replaced,
  1299. as many as specified by \param{count}.
  1300. \issue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1301. If \param{count} is supplied and negative,
  1302. the behavior is as if zero had been supplied instead.
  1303. \endissue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1304. If \param{count} is \nil, all matching items are affected.
  1305. %% 14.3.0 21
  1306. Supplying a \param{from-end} of \term{true} matters only when the
  1307. \param{count} is provided (and \term{non-nil});
  1308. in that case,
  1309. only the rightmost \param{count} \term{elements} \term{satisfying the test} are removed
  1310. (instead of the leftmost).
  1311. \param{predicate}, \param{test}, and \param{test-not}
  1312. might be called more than once for each \term{sequence} \term{element},
  1313. and their side effects can happen in any order.
  1314. %% 14.3.0 18
  1315. %% 14.3.0 23
  1316. The result of all these functions is a \term{sequence}
  1317. of the same \term{type} as \param{sequence}
  1318. that has the same elements except that those in the subsequence
  1319. \term{bounded} by \param{start} and \param{end} and \term{satisfying the test}
  1320. have been replaced by \param{newitem}.
  1321. \funref{substitute}, \funref{substitute-if}, and \funref{substitute-if-not}
  1322. return a \param{sequence} which can share with \param{sequence}
  1323. or may be \term{identical} to the input \param{sequence}
  1324. if no elements need to be changed.
  1325. \issue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1326. \funref{nsubstitute} and \funref{nsubstitute-if} are required to
  1327. \macref{setf} any \funref{car} (if \param{sequence} is a \term{list})
  1328. or \funref{aref} (if \param{sequence} is a \term{vector})
  1329. of \param{sequence} that is required to be replaced with \param{newitem}.
  1330. If \param{sequence} is a \term{list},
  1331. none of the \term{cdrs} of the top-level \term{list} can be modified.
  1332. \endissue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1333. \label Examples::
  1334. \code
  1335. (substitute #\\. #\\SPACE "0 2 4 6") \EV "0.2.4.6"
  1336. (substitute 9 4 '(1 2 4 1 3 4 5)) \EV (1 2 9 1 3 9 5)
  1337. (substitute 9 4 '(1 2 4 1 3 4 5) :count 1) \EV (1 2 9 1 3 4 5)
  1338. (substitute 9 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
  1339. \EV (1 2 4 1 3 9 5)
  1340. (substitute 9 3 '(1 2 4 1 3 4 5) :test #'>) \EV (9 9 4 9 3 4 5)
  1341. (substitute-if 0 #'evenp '((1) (2) (3) (4)) :start 2 :key #'car)
  1342. \EV ((1) (2) (3) 0)
  1343. (substitute-if 9 #'oddp '(1 2 4 1 3 4 5)) \EV (9 2 4 9 9 4 9)
  1344. (substitute-if 9 #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
  1345. \EV (1 2 4 1 3 9 5)
  1346. (setq some-things (list 'a 'car 'b 'cdr 'c)) \EV (A CAR B CDR C)
  1347. (nsubstitute-if "function was here" #'fboundp some-things
  1348. :count 1 :from-end t) \EV (A CAR B "function was here" C)
  1349. some-things \EV (A CAR B "function was here" C)
  1350. (setq alpha-tester (copy-seq "ab ")) \EV "ab "
  1351. (nsubstitute-if-not #\\z #'alpha-char-p alpha-tester) \EV "abz"
  1352. alpha-tester \EV "abz"
  1353. \endcode
  1354. \label Side Effects::
  1355. \funref{nsubstitute}, \funref{nsubstitute-if}, and \funref{nsubstitute-if-not}
  1356. modify \param{sequence}.
  1357. \label Affected By:\None.
  1358. \label Exceptional Situations::
  1359. \Lazychecktype{sequence}{a \term{proper sequence}}
  1360. \label See Also::
  1361. \funref{subst},
  1362. \funref{nsubst},
  1363. \issue{CONSTANT-MODIFICATION:DISALLOW}
  1364. {\secref\ConstantModification},
  1365. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  1366. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1367. {\secref\TraversalRules}
  1368. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1369. \label Notes::
  1370. %% Moved from Description per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1371. %% -kmp 9-May-94
  1372. If \param{sequence} is a \term{vector},
  1373. the result might or might not be simple,
  1374. and might or might not be \term{identical} to \param{sequence}.
  1375. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1376. The \kwd{test-not} \term{argument} is deprecated.
  1377. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1378. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1379. The functions \funref{substitute-if-not} and \funref{nsubstitute-if-not} are deprecated.
  1380. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1381. \funref{nsubstitute} and \funref{nsubstitute-if} can be used
  1382. in for-effect-only positions in code.
  1383. Because the side-effecting variants (\eg \funref{nsubstitute})
  1384. potentially change the path that is being traversed, their effects in
  1385. the presence of shared or circular structure may vary in surprising ways when
  1386. compared to their non-side-effecting alternatives. To see this,
  1387. consider the following side-effect behavior, which might be exhibited by
  1388. some implementations:
  1389. \code
  1390. (defun test-it (fn)
  1391. (let ((x (cons 'b nil)))
  1392. (rplacd x x)
  1393. (funcall fn 'a 'b x :count 1)))
  1394. (test-it #'substitute) \EV (A . #1=(B . #1#))
  1395. (test-it #'nsubstitute) \EV (A . #1#)
  1396. \endcode
  1397. \endcom
  1398. %-------------------- Sequence Joining --------------------
  1399. %%% ========== CONCATENATE
  1400. \begincom{concatenate}\ftype{Function}
  1401. \label Syntax::
  1402. \DefunWithValues concatenate {result-type {\rest} sequences} {result-sequence}
  1403. \label Arguments and Values::
  1404. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1405. \param{result-type}---a \typeref{sequence} \term{type specifier}.
  1406. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1407. \param{sequences}---a \term{sequence}.
  1408. \param{result-sequence}---a \term{proper sequence} of \term{type} \param{result-type}.
  1409. \label Description::
  1410. %% 14.2.0 3
  1411. \funref{concatenate} returns a \term{sequence} that contains
  1412. all the individual elements of all the \param{sequences} in the order
  1413. that they are supplied.
  1414. The \term{sequence} is of type \param{result-type},
  1415. which must be a \subtypeof{sequence}.
  1416. All of the \param{sequences} are copied from; the result
  1417. does not share any structure with any of the \param{sequences}.
  1418. %% 14.2.0 4
  1419. Therefore, if only one \param{sequence} is provided
  1420. and it is of type \param{result-type},
  1421. \funref{concatenate} is required to copy \param{sequence} rather than simply
  1422. returning it.
  1423. It is an error if any element of the \param{sequences} cannot be an
  1424. element of the \term{sequence} result.
  1425. \reviewer{Barmar: Should signal?}%!!!
  1426. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1427. If the \param{result-type} is a \term{subtype} of \typeref{list},
  1428. the result will be a \term{list}.
  1429. If the \param{result-type} is a \term{subtype} of \typeref{vector},
  1430. then if the implementation can determine the element type specified
  1431. for the \param{result-type}, the element type of the resulting array
  1432. is the result of \term{upgrading} that element type; or, if the
  1433. implementation can determine that the element type is unspecified (or \f{*}),
  1434. the element type of the resulting array is \typeref{t};
  1435. otherwise, an error is signaled.
  1436. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1437. \label Examples::
  1438. \code
  1439. (concatenate 'string "all" " " "together" " " "now") \EV "all together now"
  1440. (concatenate 'list "ABC" '(d e f) #(1 2 3) #*1011)
  1441. \EV (#\\A #\\B #\\C D E F 1 2 3 1 0 1 1)
  1442. (concatenate 'list) \EV NIL
  1443. \endcode
  1444. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1445. \code
  1446. (concatenate '(vector * 2) "a" "bc") should signal an error
  1447. \endcode
  1448. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1449. \label Affected By:\None.
  1450. \label Exceptional Situations::
  1451. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1452. An error is signaled if the \param{result-type} is neither
  1453. a \term{recognizable subtype} of \typeref{list},
  1454. nor a \term{recognizable subtype} of \typeref{vector}.
  1455. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1456. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1457. An error \oftype{type-error} should be signaled if \param{result-type}
  1458. specifies the number of elements and the sum of \param{sequences}
  1459. is different from that number.
  1460. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1461. \label See Also::
  1462. \funref{append}
  1463. \label Notes:\None.
  1464. \endcom
  1465. %%% ========== MERGE
  1466. \begincom{merge}\ftype{Function}
  1467. \label Syntax::
  1468. \DefunWithValues merge
  1469. {result-type sequence-1 sequence-2 predicate {\key} key}
  1470. {result-sequence}
  1471. \label Arguments and Values::
  1472. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1473. \param{result-type}---a \typeref{sequence} \term{type specifier}.
  1474. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1475. \param{sequence-1}---a \term{sequence}.
  1476. \param{sequence-2}---a \term{sequence}.
  1477. \param{predicate}---a \term{designator} for
  1478. a \term{function} of two arguments that returns a \term{generalized boolean}.
  1479. %% 14.4.0 12
  1480. \param{key}---a \term{designator} for a \term{function} of one argument,
  1481. or \nil.
  1482. \param{result-sequence}---a \term{proper sequence} of \term{type} \param{result-type}.
  1483. \label Description::
  1484. %% 14.4.0 10
  1485. Destructively merges \param{sequence-1} with \param{sequence-2} according
  1486. to an order determined by the \param{predicate}. \funref{merge} determines
  1487. the relationship between two elements by giving keys extracted from the
  1488. sequence elements to the \param{predicate}.
  1489. The first argument to the \param{predicate} function is an element of
  1490. \param{sequence-1} as returned by the \param{key} (if supplied);
  1491. the second argument is an element of \param{sequence-2} as returned by
  1492. the \param{key} (if supplied).
  1493. \param{Predicate} should return \term{true} if and only if its first
  1494. argument is strictly less than the second (in some appropriate sense).
  1495. If the first argument is greater than or equal to the second
  1496. (in the appropriate sense), then \param{predicate} should return \term{false}.
  1497. \funref{merge}
  1498. considers two elements \f{x} and \f{y} to be equal if
  1499. \f{(funcall predicate x y)} and
  1500. \f{(funcall predicate y x)} both \term{yield} \term{false}.
  1501. %% 14.4.0 11
  1502. %% 14.4.0 12
  1503. The argument to the \param{key} is the \param{sequence} element.
  1504. Typically, the return value of the \param{key}
  1505. becomes the argument to \param{predicate}.
  1506. If \param{key} is not supplied or \nil, the sequence element itself is used.
  1507. The \param{key} may be executed more than once for each \term{sequence} \term{element},
  1508. and its side effects may occur in any order.
  1509. %% 14.4.0 13
  1510. If \param{key} and \param{predicate} return, then the merging operation
  1511. will terminate. The result of merging two \term{sequences} \f{x} and \f{y}
  1512. is a new \term{sequence} of type \param{result-type} \f{z},
  1513. such that the length of \f{z} is the sum of the lengths of \f{x}
  1514. and \f{y}, and \f{z} contains all the elements of \f{x} and \f{y}.
  1515. If \f{x1} and \f{x2} are two elements of \f{x}, and \f{x1} precedes
  1516. \f{x2} in \f{x}, then \f{x1} precedes \f{x2} in \f{z}, and similarly for
  1517. elements of \f{y}. In short, \f{z} is an interleaving of \f{x} and \f{y}.
  1518. %% 14.4.0 14
  1519. If \f{x} and \f{y} were correctly sorted according to the
  1520. \param{predicate}, then \f{z} will also be correctly sorted.
  1521. If \f{x} or \f{y} is not so sorted, then \f{z} will not be sorted,
  1522. but will nevertheless be an interleaving of \f{x} and \f{y}.
  1523. %% 14.4.0 14
  1524. The merging operation is guaranteed stable;
  1525. if two or more elements are considered equal by the \param{predicate},
  1526. then the elements from \param{sequence-1} will
  1527. precede those from \param{sequence-2} in the result.
  1528. \param{sequence-1} and/or \param{sequence-2} may be destroyed.
  1529. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1530. If the \param{result-type} is a \term{subtype} of \typeref{list},
  1531. the result will be a \term{list}.
  1532. If the \param{result-type} is a \term{subtype} of \typeref{vector},
  1533. then if the implementation can determine the element type specified
  1534. for the \param{result-type}, the element type of the resulting array
  1535. is the result of \term{upgrading} that element type; or, if the
  1536. implementation can determine that the element type is unspecified (or \f{*}),
  1537. the element type of the resulting array is \typeref{t};
  1538. otherwise, an error is signaled.
  1539. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1540. \label Examples::
  1541. \code
  1542. (setq test1 (list 1 3 4 6 7))
  1543. (setq test2 (list 2 5 8))
  1544. (merge 'list test1 test2 #'<) \EV (1 2 3 4 5 6 7 8)
  1545. (setq test1 (copy-seq "BOY"))
  1546. (setq test2 (copy-seq :nosy"))
  1547. (merge 'string test1 test2 #'char-lessp) \EV "BnOosYy"
  1548. (setq test1 (vector ((red . 1) (blue . 4))))
  1549. (setq test2 (vector ((yellow . 2) (green . 7))))
  1550. (merge 'vector test1 test2 #'< :key #'cdr)
  1551. \EV #((RED . 1) (YELLOW . 2) (BLUE . 4) (GREEN . 7))
  1552. \endcode
  1553. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1554. \code
  1555. (merge '(vector * 4) '(1 5) '(2 4 6) #'<) should signal an error
  1556. \endcode
  1557. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1558. \label Affected By:\None.
  1559. \label Exceptional Situations::
  1560. \issue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1561. An error must be signaled if the \param{result-type} is neither
  1562. a \term{recognizable subtype} of \typeref{list},
  1563. nor a \term{recognizable subtype} of \typeref{vector}.
  1564. \endissue{CONCATENATE-SEQUENCE:SIGNAL-ERROR}
  1565. \issue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1566. An error \oftype{type-error} should be signaled
  1567. if \param{result-type} specifies the number of elements
  1568. and the sum of the lengths of \param{sequence-1} and \param{sequence-2}
  1569. is different from that number.
  1570. \endissue{SEQUENCE-TYPE-LENGTH:MUST-MATCH}
  1571. \label See Also::
  1572. \funref{sort},
  1573. \funref{stable-sort},
  1574. \issue{CONSTANT-MODIFICATION:DISALLOW}
  1575. {\secref\ConstantModification},
  1576. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  1577. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1578. {\secref\TraversalRules}
  1579. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1580. \label Notes:\None.
  1581. \endcom
  1582. %-------------------- Sequence Deletion --------------------
  1583. %%% ========== REMOVE
  1584. %%% ========== REMOVE-IF
  1585. %%% ========== REMOVE-IF-NOT
  1586. %%% ========== DELETE
  1587. %%% ========== DELETE-IF
  1588. %%% ========== DELETE-IF-NOT
  1589. \begincom{remove, remove-if, remove-if-not,
  1590. delete, delete-if, delete-if-not}\ftype{Function}
  1591. \label Syntax::
  1592. \DefunWithValues remove
  1593. {item sequence {\key} from-end test test-not start end count key}
  1594. {result-sequence}
  1595. \DefunWithValues remove-if
  1596. {test sequence {\key} from-end start end count key}
  1597. {result-sequence}
  1598. \DefunWithValues remove-if-not
  1599. {test sequence {\key} from-end start end count key}
  1600. {result-sequence}
  1601. \DefunWithValues delete
  1602. {item sequence {\key} from-end test test-not start end count key}
  1603. {result-sequence}
  1604. \DefunWithValues delete-if
  1605. {test sequence {\key} from-end start end count key}
  1606. {result-sequence}
  1607. \DefunWithValues delete-if-not
  1608. {test sequence {\key} from-end start end count key}
  1609. {result-sequence}
  1610. \label Arguments and Values::
  1611. \param{item}---an \term{object}.
  1612. \param{sequence}---a \term{proper sequence}.
  1613. \param{test}---a \term{designator} for a \term{function}
  1614. of one \term{argument} that returns a \term{generalized boolean}.
  1615. \param{from-end}---a \term{generalized boolean}.
  1616. \Default{\term{false}}
  1617. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  1618. that returns a \term{generalized boolean}.
  1619. \param{test-not}---a \term{designator} for
  1620. a \term{function} of two \term{arguments}
  1621. that returns a \term{generalized boolean}.
  1622. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1623. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1624. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  1625. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  1626. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1627. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1628. \issue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1629. \param{count}---an \term{integer} or \nil.
  1630. \endissue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1631. \Default{\nil}
  1632. \param{key}---a \term{designator} for a \term{function} of one argument,
  1633. or \nil.
  1634. \param{result-sequence}---a \term{sequence}.
  1635. \label Description::
  1636. \funref{remove}, \funref{remove-if}, and \funref{remove-if-not}
  1637. return a \param{sequence} from which
  1638. the elements that \term{satisfy the test}
  1639. have been removed.
  1640. \funref{delete}, \funref{delete-if}, and \funref{delete-if-not}
  1641. are like \funref{remove}, \funref{remove-if}, and
  1642. \funref{remove-if-not} respectively,
  1643. but they may modify \param{sequence}.
  1644. %% Moon's suggested interpretation follows:
  1645. If \param{sequence} is a \term{vector}, the result is a
  1646. \term{vector} that has the same
  1647. \term{actual array element type} as \param{sequence}.
  1648. %% Moved to notes per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1649. %% -kmp 9-May-94
  1650. % The result might or might not be simple,
  1651. % and might or might not be \term{identical} to \param{sequence}.
  1652. %% Another possible interpretation:
  1653. %% The result might or might not be \term{identical} to \param{sequence}.
  1654. %% If the result is a \term{vector} that is not \term{identical}
  1655. %% to \param{sequence}, the result is a \term{fresh} \term{simple array}
  1656. %% of \term{rank} one.
  1657. If \param{sequence} is a \term{list}, the result is a \term{list}.
  1658. %% End Moon's suggested interpretation.
  1659. %% 14.3.0 8
  1660. %% 14.3.0 11
  1661. Supplying a \param{from-end} of \term{true} matters only when the
  1662. \param{count} is provided; in that case only the rightmost \param{count} elements
  1663. \term{satisfying the test} are deleted.
  1664. %% 14.3.0 7
  1665. %% 14.3.0 10
  1666. \param{Count}, if supplied, limits the number of elements
  1667. removed or deleted; if more than \param{count} elements \term{satisfy the test},
  1668. then of these elements only the leftmost or rightmost, depending on
  1669. \param{from-end},
  1670. are deleted or removed,
  1671. as many as specified by \param{count}.
  1672. \issue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1673. If \param{count} is supplied and negative,
  1674. the behavior is as if zero had been supplied instead.
  1675. \endissue{RANGE-OF-COUNT-KEYWORD:NIL-OR-INTEGER}
  1676. If \param{count} is \nil, all matching items are affected.
  1677. For all these functions,
  1678. elements
  1679. not removed or deleted occur in the same order in the result
  1680. as they did in \param{sequence}.
  1681. %% 14.3.0 6
  1682. \funref{remove}, \funref{remove-if}, \funref{remove-if-not} return
  1683. a \term{sequence}
  1684. of the same \term{type} as \param{sequence}
  1685. that has the same elements except that those in the subsequence
  1686. \term{bounded} by \param{start} and \param{end} and \term{satisfying the test}
  1687. have been removed.
  1688. This is a non-destructive operation. If any
  1689. elements need to be removed, the result will be a copy.
  1690. The result of \funref{remove} may share
  1691. with \param{sequence};
  1692. the result may be \term{identical} to the input \param{sequence}
  1693. if no elements need to be removed.
  1694. %% 14.3.0 9
  1695. \funref{delete}, \funref{delete-if}, and \funref{delete-if-not}
  1696. return a \term{sequence}
  1697. of the same \term{type} as \param{sequence}
  1698. that has the same elements except that those in the subsequence
  1699. \term{bounded} by \param{start} and \param{end} and \term{satisfying the test}
  1700. have been deleted.
  1701. \param{Sequence} may be destroyed and used to construct
  1702. the result; however, the result might or might not be \term{identical}
  1703. to \param{sequence}.
  1704. \issue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1705. \funref{delete}, when \param{sequence} is a \term{list}, is permitted to
  1706. \macref{setf} any part, \funref{car} or \funref{cdr}, of the
  1707. top-level list structure in that \param{sequence}.
  1708. When \param{sequence} is a \term{vector}, \funref{delete} is
  1709. permitted to change the dimensions of the \term{vector}
  1710. and to slide its elements into new positions without
  1711. permuting them to produce the resulting \term{vector}.
  1712. \funref{delete-if} is constrained to behave exactly as follows:
  1713. \code
  1714. (delete nil \i{sequence}
  1715. :test #'(lambda (ignore \i{item}) (funcall \i{test} \i{item}))
  1716. ...)
  1717. \endcode
  1718. \endissue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1719. \label Examples::
  1720. \code
  1721. (remove 4 '(1 3 4 5 9)) \EV (1 3 5 9)
  1722. (remove 4 '(1 2 4 1 3 4 5)) \EV (1 2 1 3 5)
  1723. (remove 4 '(1 2 4 1 3 4 5) :count 1) \EV (1 2 1 3 4 5)
  1724. (remove 4 '(1 2 4 1 3 4 5) :count 1 :from-end t) \EV (1 2 4 1 3 5)
  1725. (remove 3 '(1 2 4 1 3 4 5) :test #'>) \EV (4 3 4 5)
  1726. (setq lst '(list of four elements)) \EV (LIST OF FOUR ELEMENTS)
  1727. (setq lst2 (copy-seq lst)) \EV (LIST OF FOUR ELEMENTS)
  1728. (setq lst3 (delete 'four lst)) \EV (LIST OF ELEMENTS)
  1729. (equal lst lst2) \EV \term{false}
  1730. (remove-if #'oddp '(1 2 4 1 3 4 5)) \EV (2 4 4)
  1731. (remove-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
  1732. \EV (1 2 4 1 3 5)
  1733. (remove-if-not #'evenp '(1 2 3 4 5 6 7 8 9) :count 2 :from-end t)
  1734. \EV (1 2 3 4 5 6 8)
  1735. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1736. (delete 4 tester) \EV (1 2 1 3 5)
  1737. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1738. (delete 4 tester :count 1) \EV (1 2 1 3 4 5)
  1739. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1740. (delete 4 tester :count 1 :from-end t) \EV (1 2 4 1 3 5)
  1741. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1742. (delete 3 tester :test #'>) \EV (4 3 4 5)
  1743. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1744. (delete-if #'oddp tester) \EV (2 4 4)
  1745. (setq tester (list 1 2 4 1 3 4 5)) \EV (1 2 4 1 3 4 5)
  1746. (delete-if #'evenp tester :count 1 :from-end t) \EV (1 2 4 1 3 5)
  1747. (setq tester (list 1 2 3 4 5 6)) \EV (1 2 3 4 5 6)
  1748. (delete-if #'evenp tester) \EV (1 3 5)
  1749. tester \EV \term{implementation-dependent}
  1750. \endcode
  1751. %!!! This example (with the "or") looks like bad notation AND questionable value
  1752. \issue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1753. \code
  1754. (setq foo (list 'a 'b 'c)) \EV (A B C)
  1755. (setq bar (cdr foo)) \EV (B C)
  1756. (setq foo (delete 'b foo)) \EV (A C)
  1757. bar \EV ((C)) or ...
  1758. (eq (cdr foo) (car bar)) \EV T or ...
  1759. \endcode
  1760. \endissue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1761. \label Side Effects::
  1762. For \funref{delete}, \funref{delete-if}, and \funref{delete-if-not},
  1763. \param{sequence} may be destroyed and used to construct the result.
  1764. \label Affected By:\None.
  1765. \label Exceptional Situations::
  1766. \Lazychecktype{sequence}{a \term{proper sequence}}
  1767. \label See Also::
  1768. \issue{CONSTANT-MODIFICATION:DISALLOW}
  1769. {\secref\ConstantModification},
  1770. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  1771. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1772. {\secref\TraversalRules}
  1773. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1774. \label Notes::
  1775. %% Moved from Description per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1776. %% -kmp 9-May-94
  1777. If \param{sequence} is a \term{vector},
  1778. the result might or might not be simple,
  1779. and might or might not be \term{identical} to \param{sequence}.
  1780. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1781. The \kwd{test-not} \term{argument} is deprecated.
  1782. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1783. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1784. The functions \funref{delete-if-not} and \funref{remove-if-not} are deprecated.
  1785. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1786. \endcom
  1787. %%% ========== REMOVE-DUPLICATES
  1788. %%% ========== DELETE-DUPLICATES
  1789. \begincom{remove-duplicates, delete-duplicates}\ftype{Function}
  1790. \label Syntax::
  1791. \DefunWithValuesNewline remove-duplicates
  1792. {sequence {\key}
  1793. \vtop{\hbox{from-end test test-not}
  1794. \hbox{start end key}}}
  1795. {result-sequence}
  1796. \DefunWithValuesNewline delete-duplicates
  1797. {sequence {\key}
  1798. \vtop{\hbox{from-end test test-not}
  1799. \hbox{start end key}}}
  1800. {result-sequence}
  1801. \label Arguments and Values::
  1802. \param{sequence}---a \term{proper sequence}.
  1803. \param{from-end}---a \term{generalized boolean}.
  1804. \Default{\term{false}}
  1805. \param{test}---a \term{designator} for a \term{function} of two \term{arguments}
  1806. that returns a \term{generalized boolean}.
  1807. \param{test-not}---a \term{designator} for
  1808. a \term{function} of two \term{arguments}
  1809. that returns a \term{generalized boolean}.
  1810. \issue{SUBSEQ-OUT-OF-BOUNDS}
  1811. \issue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1812. \param{start}, \param{end}---\term{bounding index designators} of \param{sequence}.
  1813. \Defaults{\param{start} and \param{end}}{\f{0} and \nil}
  1814. \endissue{RANGE-OF-START-AND-END-PARAMETERS:INTEGER-AND-INTEGER-NIL}
  1815. \endissue{SUBSEQ-OUT-OF-BOUNDS}
  1816. \param{key}---a \term{designator} for a \term{function} of one argument,
  1817. or \nil.
  1818. \param{result-sequence}---a \term{sequence}.
  1819. \label Description::
  1820. \funref{remove-duplicates} returns a modified copy of \param{sequence}
  1821. from which any element that matches another element occurring in
  1822. \param{sequence} has been removed.
  1823. %% Moon's suggested interpretation follows:
  1824. If \param{sequence} is a \term{vector}, the result is a
  1825. \term{vector} that has the same
  1826. \term{actual array element type} as \param{sequence}.
  1827. %% Moved to notes per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1828. %% -kmp 9-May-94
  1829. % The result might or might not be simple,
  1830. % and might or might not be \term{identical} to \param{sequence}.
  1831. %% Another possible interpretation:
  1832. %% The result might or might not be \term{identical} to \param{sequence}.
  1833. %% If the result is a \term{vector} that is not \term{identical}
  1834. %% to \param{sequence}, the result is a \term{fresh} \term{simple array}
  1835. %% of \term{rank} one.
  1836. If \param{sequence} is a \term{list}, the result is a \term{list}.
  1837. %% End Moon's suggested interpretation.
  1838. \funref{delete-duplicates} is like \funref{remove-duplicates},
  1839. but \funref{delete-duplicates} may modify \param{sequence}.
  1840. %% 14.3.0 13
  1841. The elements of \param{sequence} are compared \term{pairwise}, and if any two match,
  1842. then the one occurring earlier in \param{sequence}
  1843. is discarded, unless \param{from-end} is \term{true}, in which case the one
  1844. later in \param{sequence} is discarded.
  1845. \funref{remove-duplicates} and \funref{delete-duplicates}
  1846. return a \term{sequence} of the same \term{type} as
  1847. \param{sequence} with enough elements removed so that no two of the remaining
  1848. elements match. The order of the elements remaining in the result
  1849. is the same as the order in which they appear in \param{sequence}.
  1850. \funref{remove-duplicates} returns a \term{sequence}
  1851. %% 14.3.0 14
  1852. that may share
  1853. with \param{sequence} or may be \term{identical} to \param{sequence}
  1854. if no elements need to be removed.
  1855. \issue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1856. \funref{delete-duplicates}, when \param{sequence} is a \term{list},
  1857. is permitted to \macref{setf} any part, \funref{car} or \funref{cdr},
  1858. of the top-level list structure in that \param{sequence}.
  1859. When \param{sequence} is a \term{vector}, \funref{delete-duplicates}
  1860. is permitted to change the dimensions of the \term{vector}
  1861. and to slide its elements into new positions without
  1862. permuting them to produce the resulting \term{vector}.
  1863. \endissue{REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89}
  1864. \label Examples::
  1865. %% 14.3.0 16
  1866. \code
  1867. (remove-duplicates "aBcDAbCd" :test #'char-equal :from-end t) \EV "aBcD"
  1868. (remove-duplicates '(a b c b d d e)) \EV (A C B D E)
  1869. (remove-duplicates '(a b c b d d e) :from-end t) \EV (A B C D E)
  1870. (remove-duplicates '((foo #\\a) (bar #\\%) (baz #\\A))
  1871. :test #'char-equal :key #'cadr) \EV ((BAR #\\%) (BAZ #\\A))
  1872. (remove-duplicates '((foo #\\a) (bar #\\%) (baz #\\A))
  1873. :test #'char-equal :key #'cadr :from-end t) \EV ((FOO #\\a) (BAR #\\%))
  1874. (setq tester (list 0 1 2 3 4 5 6))
  1875. (delete-duplicates tester :key #'oddp :start 1 :end 6) \EV (0 4 5 6)
  1876. \endcode
  1877. \label Side Effects::
  1878. %% 14.3.0 15
  1879. \funref{delete-duplicates} might destructively modify \param{sequence}.
  1880. \label Affected By:\None.
  1881. \label Exceptional Situations::
  1882. \Shouldchecktype{sequence}{a \term{proper sequence}}
  1883. \label See Also::
  1884. \issue{CONSTANT-MODIFICATION:DISALLOW}
  1885. {\secref\ConstantModification},
  1886. \endissue{CONSTANT-MODIFICATION:DISALLOW}
  1887. \issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1888. {\secref\TraversalRules}
  1889. \endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
  1890. \label Notes::
  1891. %% Moved from Description per Schulenburg #1 (by X3J13 vote at May 4-5, 1994 meeting).
  1892. %% -kmp 9-May-94
  1893. If \param{sequence} is a \term{vector},
  1894. the result might or might not be simple,
  1895. and might or might not be \term{identical} to \param{sequence}.
  1896. \issue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1897. The \kwd{test-not} \term{argument} is deprecated.
  1898. \endissue{TEST-NOT-IF-NOT:FLUSH-ALL}
  1899. %% 14.3.0 17
  1900. These functions are useful for converting \param{sequence} into a canonical
  1901. form suitable for representing a set.
  1902. \endcom