Mercurial > hg > xemacs-beta

comparison man/lispref/lists.texi @ 5182:2e528066e2fc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move #'sort*, #'fill, #'merge to C from cl-seq.el. lisp/ChangeLog addition: 2010-04-01 Aidan Kehoe <kehoea@parhasard.net> * cl-seq.el (fill, sort*, merge): Move these functions to fns.c. (stable-sort): Make this docstring reflect the argument names used in the #'sort* docstring. * cl-macs.el (stable-sort): Make #'stable-sort exactly equivalent to #'sort* in compiled code. * bytecomp.el (byte-compile-maybe-add-*): New macro, for functions like #'sort and #'mapcar that, to be strictly compatible, should only take two args, but in our implementation can take more, because they're aliases of #'sort* and #'mapcar*. (byte-compile-mapcar, byte-compile-sort, byte-compile-fillarray): Use this new macro. (map-into): Add a byte-compile method for #'map-into in passing. * apropos.el (apropos-print): Use #'sort* with a :key argument, now it's in C. * compat.el (extent-at): Ditto. * register.el (list-registers): Ditto. * package-ui.el (pui-list-packages): Ditto. * help.el (sorted-key-descriptions): Ditto. src/ChangeLog addition: 2010-03-31 Aidan Kehoe <kehoea@parhasard.net> * fns.c (STRING_DATA_TO_OBJECT_ARRAY) (BIT_VECTOR_TO_OBJECT_ARRAY, c_merge_predicate_key) (c_merge_predicate_nokey, list_merge, array_merge) (list_array_merge_into_list, list_list_merge_into_array) (list_array_merge_into_array, CHECK_KEY_ARGUMENT, Fmerge) (list_sort, array_sort, FsortX): Move #'sort*, #'fill, #'merge from cl-seq.el to C, extending the implementations of Fsort, Ffillarray, and merge() to do so. * keymap.c (keymap_submaps, map_keymap_sort_predicate) (describe_map_sort_predicate): Change the calling semantics of the C sort predicates to return a non-nil Lisp object if the first argument is less than the second, rather than C integers. * fontcolor-msw.c (sort_font_list_function): * fileio.c (build_annotations): * dired.c (Fdirectory_files): * abbrev.c (Finsert_abbrev_table_description): Call list_sort instead of Fsort, list_merge instead of merge() in these functions. man/ChangeLog addition: 2010-04-01 Aidan Kehoe <kehoea@parhasard.net> * lispref/lists.texi (Rearrangement): Update the documentation of #'sort here, now that it accepts any type of sequence and the KEY keyword argument. (Though this is probably now the wrong place for this function, given that.)
author Aidan Kehoe <kehoea@parhasard.net>
date Thu, 01 Apr 2010 20:22:50 +0100
parents b880e7bdec21
children 9f738305f80f
comparison
equal deleted inserted replaced
5181:a00bfbd64e0a 5182:2e528066e2fc
1048 ------------- ------------ 1048 ------------- ------------
1049 @end group 1049 @end group
1050 @end smallexample 1050 @end smallexample
1051 @end defun 1051 @end defun
1052 1052
1053 @defun sort list predicate 1053 @defun sort* sequence predicate &key (key #'identity)
1054 @cindex stable sort 1054 @cindex stable sort
1055 @cindex sorting lists 1055 @cindex sorting lists
1056 This function sorts @var{list} stably, though destructively, and 1056 @cindex sorting arrays
1057 returns the sorted list. It compares elements using @var{predicate}. A 1057 @cindex sort
1058 This function sorts @var{sequence} stably, though destructively, and
1059 returns the sorted sequence. It compares elements using @var{predicate}. A
1058 stable sort is one in which elements with equal sort keys maintain their 1060 stable sort is one in which elements with equal sort keys maintain their
1059 relative order before and after the sort. Stability is important when 1061 relative order before and after the sort. Stability is important when
1060 successive sorts are used to order elements according to different 1062 successive sorts are used to order elements according to different
1061 criteria. 1063 criteria.
1062 1064
1065 @var{sequence} can be any sequence, that is, a list, a vector, a
1066 bit-vector, or a string.
1067
1063 The argument @var{predicate} must be a function that accepts two 1068 The argument @var{predicate} must be a function that accepts two
1064 arguments. It is called with two elements of @var{list}. To get an 1069 arguments. It is called with two elements of @var{sequence}. To get an
1065 increasing order sort, the @var{predicate} should return @code{t} if the 1070 increasing order sort, the @var{predicate} should return @code{t} if the
1066 first element is ``less than'' the second, or @code{nil} if not. 1071 first element is ``less than'' the second, or @code{nil} if not.
1067 1072
1068 The destructive aspect of @code{sort} is that it rearranges the cons 1073 The keyword argument @var{key}, if supplied, is a function used to
1069 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort 1074 extract an object to be used for comparison from each element of
1075 @var{sequence}, and defaults to @code{identity}. For example, to sort a
1076 vector of lists by the numeric value of the first element, you could use
1077 the following code:
1078
1079 @example
1080 @group
1081 (setq example-vector [(1 "foo") (3.14159 bar) (2 . quux)])
1082 @result{} [(1 "foo") (3.14159 bar) (2 . quux)]
1083 @end group
1084 @group
1085 (sort* example-vector #'< :key #'car)
1086 @result{} [(1 "foo") (2 . quux) (3.14159 bar)]
1087 @end group
1088 @end example
1089
1090 If @var{sequence} is a list, @code{sort*} rearranges the cons cells
1091 forming @var{sequence} by changing @sc{cdr}s. A nondestructive sort
1070 function would create new cons cells to store the elements in their 1092 function would create new cons cells to store the elements in their
1071 sorted order. If you wish to make a sorted copy without destroying the 1093 sorted order. @code{sort*} treats other sequence types in an analogous
1094 fashion---if you wish to make a sorted copy without destroying the
1072 original, copy it first with @code{copy-sequence} and then sort. 1095 original, copy it first with @code{copy-sequence} and then sort.
1073 1096
1074 Sorting does not change the @sc{car}s of the cons cells in @var{list}; 1097 Sorting will not change the @sc{car}s of the cons cells of a list
1075 the cons cell that originally contained the element @code{a} in 1098 @var{sequence}; the cons cell that originally contained the element @code{a} in
1076 @var{list} still has @code{a} in its @sc{car} after sorting, but it now 1099 @var{sequence} still has @code{a} in its @sc{car} after sorting, but it now
1077 appears in a different position in the list due to the change of 1100 appears in a different position in the sequence due to the change of
1078 @sc{cdr}s. For example: 1101 @sc{cdr}s. For example:
1079 1102
1080 @example 1103 @example
1081 @group 1104 @group
1082 (setq nums '(1 3 2 6 5 4 0)) 1105 (setq nums '(1 3 2 6 5 4 0))
1083 @result{} (1 3 2 6 5 4 0) 1106 @result{} (1 3 2 6 5 4 0)
1084 @end group 1107 @end group
1085 @group 1108 @group
1086 (sort nums '<) 1109 (sort* nums '<)
1087 @result{} (0 1 2 3 4 5 6) 1110 @result{} (0 1 2 3 4 5 6)
1088 @end group 1111 @end group
1089 @group 1112 @group
1090 nums 1113 nums
1091 @result{} (1 2 3 4 5 6) 1114 @result{} (1 2 3 4 5 6)
1094 1117
1095 @noindent 1118 @noindent
1096 Note that the list in @code{nums} no longer contains 0; this is the same 1119 Note that the list in @code{nums} no longer contains 0; this is the same
1097 cons cell that it was before, but it is no longer the first one in the 1120 cons cell that it was before, but it is no longer the first one in the
1098 list. Don't assume a variable that formerly held the argument now holds 1121 list. Don't assume a variable that formerly held the argument now holds
1099 the entire sorted list! Instead, save the result of @code{sort} and use 1122 the entire sorted list! Instead, save the result of @code{sort*} and use
1100 that. Most often we store the result back into the variable that held 1123 that. Most often we store the result back into the variable that held
1101 the original list: 1124 the original sequence:
1102 1125
1103 @example 1126 @example
1104 (setq nums (sort nums '<)) 1127 (setq nums (sort* nums '<))
1105 @end example 1128 @end example
1129
1130 In this implementation, @code{sort} is a function alias for
1131 @code{sort*}, and accepts the same arguments. In older XEmacs, and in
1132 current GNU Emacs, @code{sort} only accepted lists, and did not accept
1133 the @var{key} argument, so the byte-compiler will warn you if you call
1134 @code{sort} with more than two arguments.
1106 1135
1107 @xref{Sorting}, for more functions that perform sorting. 1136 @xref{Sorting}, for more functions that perform sorting.
1108 See @code{documentation} in @ref{Accessing Documentation}, for a 1137 See @code{documentation} in @ref{Accessing Documentation}, for a
1109 useful example of @code{sort}. 1138 useful example of @code{sort*}.
1110 @end defun 1139 @end defun
1111 1140
1112 @node Sets And Lists 1141 @node Sets And Lists
1113 @section Using Lists as Sets 1142 @section Using Lists as Sets
1114 @cindex lists as sets 1143 @cindex lists as sets