1 /* srfi-1.c --- SRFI-1 procedures for Guile
3 * Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003 Free Software
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22 #include <libguile/lang.h>
26 /* The intent of this file is to gradually replace those Scheme
27 * procedures in srfi-1.scm which extends core primitive procedures,
28 * so that using srfi-1 won't have performance penalties.
30 * Please feel free to contribute any new replacements!
34 srfi1_ilength (SCM sx
)
41 if (SCM_NULL_OR_NIL_P(hare
)) return i
;
42 if (!scm_is_pair (hare
)) return -2;
45 if (SCM_NULL_OR_NIL_P(hare
)) return i
;
46 if (!scm_is_pair (hare
)) return -2;
49 /* For every two steps the hare takes, the tortoise takes one. */
50 tortoise
= SCM_CDR(tortoise
);
52 while (! scm_is_eq (hare
, tortoise
));
54 /* If the tortoise ever catches the hare, then the list must contain
60 equal_trampoline (SCM proc
, SCM arg1
, SCM arg2
)
62 return scm_equal_p (arg1
, arg2
);
66 SCM_DEFINE (scm_srfi1_alist_copy
, "alist-copy", 1, 0, 0,
68 "Return a copy of @var{alist}, copying both the pairs comprising\n"
69 "the list and those making the associations.")
70 #define FUNC_NAME s_scm_srfi1_alist_copy
74 /* ret is the list to return. p is where to append to it, initially &ret
75 then SCM_CDRLOC of the last pair. */
79 for ( ; scm_is_pair (alist
); alist
= SCM_CDR (alist
))
81 elem
= SCM_CAR (alist
);
83 /* each element of alist must be a pair */
84 SCM_ASSERT_TYPE (scm_is_pair (elem
), alist
, SCM_ARG1
, FUNC_NAME
,
87 c
= scm_cons (scm_cons (SCM_CAR (elem
), SCM_CDR (elem
)), SCM_EOL
);
92 /* alist must be a proper list */
93 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (alist
), alist
, SCM_ARG1
, FUNC_NAME
,
100 SCM_DEFINE (scm_srfi1_break
, "break", 2, 0, 0,
102 "Return two values, the longest initial prefix of @var{lst}\n"
103 "whose elements all fail the predicate @var{pred}, and the\n"
104 "remainder of @var{lst}.\n"
106 "Note that the name @code{break} conflicts with the @code{break}\n"
107 "binding established by @code{while}. Applications wanting to\n"
108 "use @code{break} from within a @code{while} loop will need to\n"
109 "make a new define under a different name.")
110 #define FUNC_NAME s_scm_srfi1_break
112 scm_t_trampoline_1 pred_tramp
;
115 pred_tramp
= scm_trampoline_1 (pred
);
116 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
120 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
122 SCM elem
= SCM_CAR (lst
);
123 if (scm_is_true (pred_tramp (pred
, elem
)))
126 /* want this elem, tack it onto the end of ret */
127 *p
= scm_cons (elem
, SCM_EOL
);
130 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
133 return scm_values (scm_list_2 (ret
, lst
));
138 SCM_DEFINE (scm_srfi1_break_x
, "break!", 2, 0, 0,
140 "Return two values, the longest initial prefix of @var{lst}\n"
141 "whose elements all fail the predicate @var{pred}, and the\n"
142 "remainder of @var{lst}. @var{lst} may be modified to form the\n"
144 #define FUNC_NAME s_scm_srfi1_break_x
147 scm_t_trampoline_1 pred_tramp
;
149 pred_tramp
= scm_trampoline_1 (pred
);
150 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
153 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
155 if (scm_is_true (pred_tramp (pred
, SCM_CAR (upto
))))
158 /* want this element */
159 p
= SCM_CDRLOC (upto
);
161 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
165 return scm_values (scm_list_2 (lst
, upto
));
170 SCM_DEFINE (scm_srfi1_car_plus_cdr
, "car+cdr", 1, 0, 0,
172 "Return two values, the @sc{car} and the @sc{cdr} of @var{pair}.")
173 #define FUNC_NAME s_scm_srfi1_car_plus_cdr
175 SCM_VALIDATE_CONS (SCM_ARG1
, pair
);
176 return scm_values (scm_list_2 (SCM_CAR (pair
), SCM_CDR (pair
)));
181 SCM_DEFINE (scm_srfi1_concatenate
, "concatenate", 1, 0, 0,
183 "Construct a list by appending all lists in @var{lstlst}.\n"
185 "@code{concatenate} is the same as @code{(apply append\n"
186 "@var{lstlst})}. It exists because some Scheme implementations\n"
187 "have a limit on the number of arguments a function takes, which\n"
188 "the @code{apply} might exceed. In Guile there is no such\n"
190 #define FUNC_NAME s_scm_srfi1_concatenate
192 SCM_VALIDATE_LIST (SCM_ARG1
, lstlst
);
193 return scm_append (lstlst
);
198 SCM_DEFINE (scm_srfi1_concatenate_x
, "concatenate!", 1, 0, 0,
200 "Construct a list by appending all lists in @var{lstlst}. Those\n"
201 "lists may be modified to produce the result.\n"
203 "@code{concatenate!} is the same as @code{(apply append!\n"
204 "@var{lstlst})}. It exists because some Scheme implementations\n"
205 "have a limit on the number of arguments a function takes, which\n"
206 "the @code{apply} might exceed. In Guile there is no such\n"
208 #define FUNC_NAME s_scm_srfi1_concatenate
210 SCM_VALIDATE_LIST (SCM_ARG1
, lstlst
);
211 return scm_append_x (lstlst
);
216 SCM_DEFINE (scm_srfi1_count
, "count", 2, 0, 1,
217 (SCM pred
, SCM list1
, SCM rest
),
218 "Return a count of the number of times @var{pred} returns true\n"
219 "when called on elements from the given lists.\n"
221 "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n"
222 "@var{elem1} @dots{} @var{elemN})}, each element being from the\n"
223 "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n"
224 "with the first element of each list, the second with the second\n"
225 "element from each, and so on.\n"
227 "Counting stops when the end of the shortest list is reached.\n"
228 "At least one list must be non-circular.")
229 #define FUNC_NAME s_scm_srfi1_count
234 SCM_VALIDATE_REST_ARGUMENT (rest
);
238 if (scm_is_null (rest
))
241 scm_t_trampoline_1 pred_tramp
;
242 pred_tramp
= scm_trampoline_1 (pred
);
243 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
245 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
246 count
+= scm_is_true (pred_tramp (pred
, SCM_CAR (list1
)));
248 /* check below that list1 is a proper list, and done */
253 else if (scm_is_pair (rest
) && scm_is_null (SCM_CDR (rest
)))
256 scm_t_trampoline_2 pred_tramp
;
259 pred_tramp
= scm_trampoline_2 (pred
);
260 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
262 list2
= SCM_CAR (rest
);
265 if (! scm_is_pair (list1
))
267 if (! scm_is_pair (list2
))
273 count
+= scm_is_true (pred_tramp
274 (pred
, SCM_CAR (list1
), SCM_CAR (list2
)));
275 list1
= SCM_CDR (list1
);
276 list2
= SCM_CDR (list2
);
281 /* three or more lists */
285 /* vec is the list arguments */
286 vec
= scm_vector (scm_cons (list1
, rest
));
287 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
289 /* args is the argument list to pass to pred, same length as vec,
290 re-used for each call */
291 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
295 /* first elem of each list in vec into args, and step those
296 vec entries onto their next element */
297 for (i
= 0, a
= args
, argnum
= 2;
299 i
++, a
= SCM_CDR (a
), argnum
++)
301 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
302 if (! scm_is_pair (lst
))
303 goto check_lst_and_done
;
304 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for pred */
305 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
308 count
+= scm_is_true (scm_apply (pred
, args
, SCM_EOL
));
313 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
314 return scm_from_long (count
);
319 SCM_DEFINE (scm_srfi1_delete
, "delete", 2, 1, 0,
320 (SCM x
, SCM lst
, SCM pred
),
321 "Return a list containing the elements of @var{lst} but with\n"
322 "those equal to @var{x} deleted. The returned elements will be\n"
323 "in the same order as they were in @var{lst}.\n"
325 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
326 "given. An equality call is made just once for each element,\n"
327 "but the order in which the calls are made on the elements is\n"
330 "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
331 "given @var{x} is first. This means for instance elements\n"
332 "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
334 "@var{lst} is not modified, but the returned list might share a\n"
335 "common tail with @var{lst}.")
336 #define FUNC_NAME s_scm_srfi1_delete
338 scm_t_trampoline_2 equal_p
;
339 SCM ret
, *p
, keeplst
;
341 if (SCM_UNBNDP (pred
))
342 return scm_delete (x
, lst
);
344 equal_p
= scm_trampoline_2 (pred
);
345 SCM_ASSERT (equal_p
, pred
, SCM_ARG3
, FUNC_NAME
);
347 /* ret is the return list being constructed. p is where to append to it,
348 initially &ret then SCM_CDRLOC of the last pair. lst progresses as
349 elements are considered.
351 Elements to be retained are not immediately copied, instead keeplst is
352 the last pair in lst which is to be retained but not yet copied. When
353 there's no more deletions, *p can be set to keeplst to share the
354 remainder of the original lst. (The entire original lst if there's no
355 deletions at all.) */
361 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
363 if (scm_is_true (equal_p (pred
, x
, SCM_CAR (lst
))))
365 /* delete this element, so copy from keeplst (inclusive) to lst
366 (exclusive) onto ret */
367 while (! scm_is_eq (keeplst
, lst
))
369 SCM c
= scm_cons (SCM_CAR (keeplst
), SCM_EOL
);
372 keeplst
= SCM_CDR (keeplst
);
375 keeplst
= SCM_CDR (lst
);
379 /* final retained elements */
382 /* demand that lst was a proper list */
383 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
390 SCM_DEFINE (scm_srfi1_delete_x
, "delete!", 2, 1, 0,
391 (SCM x
, SCM lst
, SCM pred
),
392 "Return a list containing the elements of @var{lst} but with\n"
393 "those equal to @var{x} deleted. The returned elements will be\n"
394 "in the same order as they were in @var{lst}.\n"
396 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
397 "given. An equality call is made just once for each element,\n"
398 "but the order in which the calls are made on the elements is\n"
401 "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
402 "given @var{x} is first. This means for instance elements\n"
403 "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
405 "@var{lst} may be modified to construct the returned list.")
406 #define FUNC_NAME s_scm_srfi1_delete_x
408 scm_t_trampoline_2 equal_p
;
412 if (SCM_UNBNDP (pred
))
413 return scm_delete_x (x
, lst
);
415 equal_p
= scm_trampoline_2 (pred
);
416 SCM_ASSERT (equal_p
, pred
, SCM_ARG3
, FUNC_NAME
);
418 for (prev
= &lst
, walk
= lst
;
420 walk
= SCM_CDR (walk
))
422 if (scm_is_true (equal_p (pred
, x
, SCM_CAR (walk
))))
423 *prev
= SCM_CDR (walk
);
425 prev
= SCM_CDRLOC (walk
);
428 /* demand the input was a proper list */
429 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk
), walk
, SCM_ARG2
, FUNC_NAME
,"list");
435 SCM_DEFINE (scm_srfi1_delete_duplicates
, "delete-duplicates", 1, 1, 0,
437 "Return a list containing the elements of @var{lst} but without\n"
440 "When elements are equal, only the first in @var{lst} is\n"
441 "retained. Equal elements can be anywhere in @var{lst}, they\n"
442 "don't have to be adjacent. The returned list will have the\n"
443 "retained elements in the same order as they were in @var{lst}.\n"
445 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
446 "given. Calls @code{(pred x y)} are made with element @var{x}\n"
447 "being before @var{y} in @var{lst}. A call is made at most once\n"
448 "for each combination, but the sequence of the calls across the\n"
449 "elements is unspecified.\n"
451 "@var{lst} is not modified, but the return might share a common\n"
452 "tail with @var{lst}.\n"
454 "In the worst case, this is an @math{O(N^2)} algorithm because\n"
455 "it must check each element against all those preceding it. For\n"
456 "long lists it is more efficient to sort and then compare only\n"
457 "adjacent elements.")
458 #define FUNC_NAME s_scm_srfi1_delete_duplicates
460 scm_t_trampoline_2 equal_p
;
461 SCM ret
, *p
, keeplst
, item
, l
;
463 /* ret is the new list constructed. p is where to append, initially &ret
464 then SCM_CDRLOC of the last pair. lst is advanced as each element is
467 Elements retained are not immediately appended to ret, instead keeplst
468 is the last pair in lst which is to be kept but is not yet copied.
469 Initially this is the first pair of lst, since the first element is
472 *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all
473 the elements retained, making the equality search loop easy.
475 If an item must be deleted, elements from keeplst (inclusive) to lst
476 (exclusive) must be copied and appended to ret. When there's no more
477 deletions, *p is left set to keeplst, so ret shares structure with the
478 original lst. (ret will be the entire original lst if there are no
481 /* skip to end if an empty list (or something invalid) */
483 if (scm_is_pair (lst
))
485 if (SCM_UNBNDP (pred
))
486 equal_p
= equal_trampoline
;
489 equal_p
= scm_trampoline_2 (pred
);
490 SCM_ASSERT (equal_p
, pred
, SCM_ARG2
, FUNC_NAME
);
496 /* loop over lst elements starting from second */
500 if (! scm_is_pair (lst
))
502 item
= SCM_CAR (lst
);
504 /* loop searching ret upto lst */
505 for (l
= ret
; ! scm_is_eq (l
, lst
); l
= SCM_CDR (l
))
507 if (scm_is_true (equal_p (pred
, SCM_CAR (l
), item
)))
509 /* duplicate, don't want this element, so copy keeplst
510 (inclusive) to lst (exclusive) onto ret */
511 while (! scm_is_eq (keeplst
, lst
))
513 SCM c
= scm_cons (SCM_CAR (keeplst
), SCM_EOL
);
516 keeplst
= SCM_CDR (keeplst
);
519 keeplst
= SCM_CDR (lst
); /* elem after the one deleted */
527 /* demand that lst was a proper list */
528 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG1
, FUNC_NAME
, "list");
535 SCM_DEFINE (scm_srfi1_delete_duplicates_x
, "delete-duplicates!", 1, 1, 0,
537 "Return a list containing the elements of @var{lst} but without\n"
540 "When elements are equal, only the first in @var{lst} is\n"
541 "retained. Equal elements can be anywhere in @var{lst}, they\n"
542 "don't have to be adjacent. The returned list will have the\n"
543 "retained elements in the same order as they were in @var{lst}.\n"
545 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
546 "given. Calls @code{(pred x y)} are made with element @var{x}\n"
547 "being before @var{y} in @var{lst}. A call is made at most once\n"
548 "for each combination, but the sequence of the calls across the\n"
549 "elements is unspecified.\n"
551 "@var{lst} may be modified to construct the returned list.\n"
553 "In the worst case, this is an @math{O(N^2)} algorithm because\n"
554 "it must check each element against all those preceding it. For\n"
555 "long lists it is more efficient to sort and then compare only\n"
556 "adjacent elements.")
557 #define FUNC_NAME s_scm_srfi1_delete_duplicates_x
559 scm_t_trampoline_2 equal_p
;
560 SCM ret
, endret
, item
, l
;
562 /* ret is the return list, constructed from the pairs in lst. endret is
563 the last pair of ret, initially the first pair. lst is advanced as
564 elements are considered. */
566 /* skip to end if an empty list (or something invalid) */
568 if (scm_is_pair (lst
))
570 if (SCM_UNBNDP (pred
))
571 equal_p
= equal_trampoline
;
574 equal_p
= scm_trampoline_2 (pred
);
575 SCM_ASSERT (equal_p
, pred
, SCM_ARG2
, FUNC_NAME
);
580 /* loop over lst elements starting from second */
584 if (! scm_is_pair (lst
))
586 item
= SCM_CAR (lst
);
588 /* is item equal to any element from ret to endret (inclusive)? */
592 if (scm_is_true (equal_p (pred
, SCM_CAR (l
), item
)))
593 break; /* equal, forget this element */
595 if (scm_is_eq (l
, endret
))
597 /* not equal to any, so append this pair */
598 SCM_SETCDR (endret
, lst
);
606 /* terminate, in case last element was deleted */
607 SCM_SETCDR (endret
, SCM_EOL
);
610 /* demand that lst was a proper list */
611 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG1
, FUNC_NAME
, "list");
618 SCM_DEFINE (scm_srfi1_drop_right
, "drop-right", 2, 0, 0,
620 "Return a new list containing all except the last @var{n}\n"
621 "elements of @var{lst}.")
622 #define FUNC_NAME s_scm_srfi1_drop_right
624 SCM tail
= scm_list_tail (lst
, n
);
627 while (scm_is_pair (tail
))
629 *rend
= scm_cons (SCM_CAR (lst
), SCM_EOL
);
630 rend
= SCM_CDRLOC (*rend
);
633 tail
= SCM_CDR (tail
);
635 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
641 SCM_DEFINE (scm_srfi1_drop_right_x
, "drop-right!", 2, 0, 0,
643 "Return the a list containing the @var{n} last elements of\n"
644 "@var{lst}. @var{lst} may be modified to build the return.")
645 #define FUNC_NAME s_scm_srfi1_drop_right_x
649 if (scm_is_eq (n
, SCM_INUM0
))
652 tail
= scm_list_tail (lst
, n
);
655 /* p and tail work along the list, p being the cdrloc of the cell n steps
657 for ( ; scm_is_pair (tail
); tail
= SCM_CDR (tail
))
660 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
668 SCM_DEFINE (scm_srfi1_drop_while
, "drop-while", 2, 0, 0,
670 "Drop the longest initial prefix of @var{lst} whose elements all\n"
671 "satisfy the predicate @var{pred}.")
672 #define FUNC_NAME s_scm_srfi1_drop_while
674 scm_t_trampoline_1 pred_tramp
= scm_trampoline_1 (pred
);
675 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
677 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
678 if (scm_is_false (pred_tramp (pred
, SCM_CAR (lst
))))
681 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
688 SCM_DEFINE (scm_srfi1_eighth
, "eighth", 1, 0, 0,
690 "Return the eighth element of @var{lst}.")
691 #define FUNC_NAME s_scm_srfi1_eighth
693 return scm_list_ref (lst
, SCM_I_MAKINUM (7));
698 SCM_DEFINE (scm_srfi1_fifth
, "fifth", 1, 0, 0,
700 "Return the fifth element of @var{lst}.")
701 #define FUNC_NAME s_scm_srfi1_fifth
703 return scm_list_ref (lst
, SCM_I_MAKINUM (4));
708 SCM_DEFINE (scm_srfi1_filter_map
, "filter-map", 2, 0, 1,
709 (SCM proc
, SCM list1
, SCM rest
),
710 "Apply @var{proc} to to the elements of @var{list1} @dots{} and\n"
711 "return a list of the results as per SRFI-1 @code{map}, except\n"
712 "that any @code{#f} results are omitted from the list returned.")
713 #define FUNC_NAME s_scm_srfi1_filter_map
715 SCM ret
, *loc
, elem
, newcell
, lst
;
718 SCM_VALIDATE_REST_ARGUMENT (rest
);
723 if (scm_is_null (rest
))
726 scm_t_trampoline_1 proc_tramp
= scm_trampoline_1 (proc
);
727 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG1
, FUNC_NAME
);
729 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
731 elem
= proc_tramp (proc
, SCM_CAR (list1
));
732 if (scm_is_true (elem
))
734 newcell
= scm_cons (elem
, SCM_EOL
);
736 loc
= SCM_CDRLOC (newcell
);
740 /* check below that list1 is a proper list, and done */
745 else if (scm_is_null (SCM_CDR (rest
)))
748 scm_t_trampoline_2 proc_tramp
= scm_trampoline_2 (proc
);
749 SCM list2
= SCM_CAR (rest
);
750 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG1
, FUNC_NAME
);
754 if (! scm_is_pair (list1
))
756 if (! scm_is_pair (list2
))
760 goto check_lst_and_done
;
762 elem
= proc_tramp (proc
, SCM_CAR (list1
), SCM_CAR (list2
));
763 if (scm_is_true (elem
))
765 newcell
= scm_cons (elem
, SCM_EOL
);
767 loc
= SCM_CDRLOC (newcell
);
769 list1
= SCM_CDR (list1
);
770 list2
= SCM_CDR (list2
);
775 /* three or more lists */
779 /* vec is the list arguments */
780 vec
= scm_vector (scm_cons (list1
, rest
));
781 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
783 /* args is the argument list to pass to proc, same length as vec,
784 re-used for each call */
785 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
789 /* first elem of each list in vec into args, and step those
790 vec entries onto their next element */
791 for (i
= 0, a
= args
, argnum
= 2;
793 i
++, a
= SCM_CDR (a
), argnum
++)
795 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
796 if (! scm_is_pair (lst
))
797 goto check_lst_and_done
;
798 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for proc */
799 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
802 elem
= scm_apply (proc
, args
, SCM_EOL
);
803 if (scm_is_true (elem
))
805 newcell
= scm_cons (elem
, SCM_EOL
);
807 loc
= SCM_CDRLOC (newcell
);
813 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
819 SCM_DEFINE (scm_srfi1_find
, "find", 2, 0, 0,
821 "Return the first element of @var{lst} which satisfies the\n"
822 "predicate @var{pred}, or return @code{#f} if no such element is\n"
824 #define FUNC_NAME s_scm_srfi1_find
826 scm_t_trampoline_1 pred_tramp
= scm_trampoline_1 (pred
);
827 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
829 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
831 SCM elem
= SCM_CAR (lst
);
832 if (scm_is_true (pred_tramp (pred
, elem
)))
835 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
842 SCM_DEFINE (scm_srfi1_find_tail
, "find-tail", 2, 0, 0,
844 "Return the first pair of @var{lst} whose @sc{car} satisfies the\n"
845 "predicate @var{pred}, or return @code{#f} if no such element is\n"
847 #define FUNC_NAME s_scm_srfi1_find_tail
849 scm_t_trampoline_1 pred_tramp
= scm_trampoline_1 (pred
);
850 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
852 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
853 if (scm_is_true (pred_tramp (pred
, SCM_CAR (lst
))))
855 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
862 SCM_DEFINE (scm_srfi1_fold
, "fold", 3, 0, 1,
863 (SCM proc
, SCM init
, SCM list1
, SCM rest
),
864 "Apply @var{proc} to the elements of @var{lst1} @dots{}\n"
865 "@var{lstN} to build a result, and return that result.\n"
867 "Each @var{proc} call is @code{(@var{proc} @var{elem1} @dots{}\n"
868 "@var{elemN} @var{previous})}, where @var{elem1} is from\n"
869 "@var{lst1}, through @var{elemN} from @var{lstN}.\n"
870 "@var{previous} is the return from the previous call to\n"
871 "@var{proc}, or the given @var{init} for the first call. If any\n"
872 "list is empty, just @var{init} is returned.\n"
874 "@code{fold} works through the list elements from first to last.\n"
875 "The following shows a list reversal and the calls it makes,\n"
878 "(fold cons '() '(1 2 3))\n"
883 "@result{} (3 2 1)\n"
886 "If @var{lst1} through @var{lstN} have different lengths,\n"
887 "@code{fold} stops when the end of the shortest is reached.\n"
888 "Ie.@: elements past the length of the shortest are ignored in\n"
889 "the other @var{lst}s. At least one @var{lst} must be\n"
892 "The way @code{fold} builds a result from iterating is quite\n"
893 "general, it can do more than other iterations like say\n"
894 "@code{map} or @code{filter}. The following for example removes\n"
895 "adjacent duplicate elements from a list,\n"
898 "(define (delete-adjacent-duplicates lst)\n"
899 " (fold-right (lambda (elem ret)\n"
900 " (if (equal? elem (first ret))\n"
902 " (cons elem ret)))\n"
903 " (list (last lst))\n"
905 "(delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))\n"
906 "@result{} (1 2 3 4 5)\n"
909 "Clearly the same sort of thing can be done with a\n"
910 "@code{for-each} and a variable in which to build the result,\n"
911 "but a self-contained @var{proc} can be re-used in multiple\n"
912 "contexts, where a @code{for-each} would have to be written out\n"
914 #define FUNC_NAME s_scm_srfi1_fold
918 SCM_VALIDATE_REST_ARGUMENT (rest
);
920 if (scm_is_null (rest
))
923 scm_t_trampoline_2 proc_tramp
= scm_trampoline_2 (proc
);
924 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG1
, FUNC_NAME
);
926 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
927 init
= proc_tramp (proc
, SCM_CAR (list1
), init
);
929 /* check below that list1 is a proper list, and done */
935 /* two or more lists */
939 /* vec is the list arguments */
940 vec
= scm_vector (scm_cons (list1
, rest
));
941 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
943 /* args is the argument list to pass to proc, same length as vec,
944 re-used for each call */
945 args
= scm_make_list (SCM_I_MAKINUM (len
+1), SCM_UNDEFINED
);
949 /* first elem of each list in vec into args, and step those
950 vec entries onto their next element */
951 for (i
= 0, a
= args
, argnum
= 2;
953 i
++, a
= SCM_CDR (a
), argnum
++)
955 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
956 if (! scm_is_pair (lst
))
957 goto check_lst_and_done
;
958 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for proc */
959 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
961 SCM_SETCAR (a
, init
);
963 init
= scm_apply (proc
, args
, SCM_EOL
);
968 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
974 SCM_DEFINE (scm_srfi1_last
, "last", 1, 0, 0,
976 "Like @code{cons}, but with interchanged arguments. Useful\n"
977 "mostly when passed to higher-order procedures.")
978 #define FUNC_NAME s_scm_srfi1_last
980 SCM pair
= scm_last_pair (lst
);
981 /* scm_last_pair returns SCM_EOL for an empty list */
982 SCM_VALIDATE_CONS (SCM_ARG1
, pair
);
983 return SCM_CAR (pair
);
988 SCM_DEFINE (scm_srfi1_length_plus
, "length+", 1, 0, 0,
990 "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n"
992 #define FUNC_NAME s_scm_srfi1_length_plus
994 long len
= scm_ilength (lst
);
995 return (len
>= 0 ? SCM_I_MAKINUM (len
) : SCM_BOOL_F
);
1000 SCM_DEFINE (scm_srfi1_list_index
, "list-index", 2, 0, 1,
1001 (SCM pred
, SCM list1
, SCM rest
),
1002 "Return the index of the first set of elements, one from each of\n"
1003 "@var{lst1}@dots{}@var{lstN}, which satisfies @var{pred}.\n"
1005 "@var{pred} is called as @code{(@var{pred} elem1 @dots{}\n"
1006 "elemN)}. Searching stops when the end of the shortest\n"
1007 "@var{lst} is reached. The return index starts from 0 for the\n"
1008 "first set of elements. If no set of elements pass then the\n"
1009 "return is @code{#f}.\n"
1012 "(list-index odd? '(2 4 6 9)) @result{} 3\n"
1013 "(list-index = '(1 2 3) '(3 1 2)) @result{} #f\n"
1015 #define FUNC_NAME s_scm_srfi1_list_index
1020 SCM_VALIDATE_REST_ARGUMENT (rest
);
1022 if (scm_is_null (rest
))
1025 scm_t_trampoline_1 pred_tramp
= scm_trampoline_1 (pred
);
1026 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
1028 for ( ; scm_is_pair (list1
); n
++, list1
= SCM_CDR (list1
))
1029 if (scm_is_true (pred_tramp (pred
, SCM_CAR (list1
))))
1030 return SCM_I_MAKINUM (n
);
1032 /* not found, check below that list1 is a proper list */
1037 else if (scm_is_pair (rest
) && scm_is_null (SCM_CDR (rest
)))
1040 SCM list2
= SCM_CAR (rest
);
1041 scm_t_trampoline_2 pred_tramp
= scm_trampoline_2 (pred
);
1042 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
1046 if (! scm_is_pair (list1
))
1048 if (! scm_is_pair (list2
))
1054 if (scm_is_true (pred_tramp (pred
,
1055 SCM_CAR (list1
), SCM_CAR (list2
))))
1056 return SCM_I_MAKINUM (n
);
1058 list1
= SCM_CDR (list1
);
1059 list2
= SCM_CDR (list2
);
1064 /* three or more lists */
1068 /* vec is the list arguments */
1069 vec
= scm_vector (scm_cons (list1
, rest
));
1070 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
1072 /* args is the argument list to pass to pred, same length as vec,
1073 re-used for each call */
1074 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
1078 /* first elem of each list in vec into args, and step those
1079 vec entries onto their next element */
1080 for (i
= 0, a
= args
, argnum
= 2;
1082 i
++, a
= SCM_CDR (a
), argnum
++)
1084 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
1085 if (! scm_is_pair (lst
))
1086 goto not_found_check_lst
;
1087 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for pred */
1088 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
1091 if (scm_is_true (scm_apply (pred
, args
, SCM_EOL
)))
1092 return SCM_I_MAKINUM (n
);
1096 not_found_check_lst
:
1097 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
1103 /* This routine differs from the core list-copy in allowing improper lists.
1104 Maybe the core could allow them similarly. */
1106 SCM_DEFINE (scm_srfi1_list_copy
, "list-copy", 1, 0, 0,
1108 "Return a copy of the given list @var{lst}.\n"
1110 "@var{lst} can be a proper or improper list. And if @var{lst}\n"
1111 "is not a pair then it's treated as the final tail of an\n"
1112 "improper list and simply returned.")
1113 #define FUNC_NAME s_scm_srfi1_list_copy
1120 fill_here
= &newlst
;
1123 while (scm_is_pair (from_here
))
1126 c
= scm_cons (SCM_CAR (from_here
), SCM_CDR (from_here
));
1128 fill_here
= SCM_CDRLOC (c
);
1129 from_here
= SCM_CDR (from_here
);
1136 SCM_DEFINE (scm_srfi1_list_tabulate
, "list-tabulate", 2, 0, 0,
1138 "Return an @var{n}-element list, where each list element is\n"
1139 "produced by applying the procedure @var{init-proc} to the\n"
1140 "corresponding list index. The order in which @var{init-proc}\n"
1141 "is applied to the indices is not specified.")
1142 #define FUNC_NAME s_scm_srfi1_list_tabulate
1145 scm_t_trampoline_1 proc_tramp
= scm_trampoline_1 (proc
);
1148 nn
= scm_to_signed_integer (n
, 0, LONG_MAX
);
1149 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG2
, FUNC_NAME
);
1151 for (i
= nn
-1; i
>= 0; i
--)
1152 ret
= scm_cons (proc_tramp (proc
, scm_from_long (i
)), ret
);
1159 SCM_DEFINE (scm_srfi1_lset_adjoin
, "lset-adjoin", 2, 0, 1,
1160 (SCM equal
, SCM lst
, SCM rest
),
1161 "Add to @var{list} any of the given @var{elem}s not already in\n"
1162 "the list. @var{elem}s are @code{cons}ed onto the start of\n"
1163 "@var{list} (so the return shares a common tail with\n"
1164 "@var{list}), but the order they're added is unspecified.\n"
1166 "The given @var{=} procedure is used for comparing elements,\n"
1167 "called as @code{(@var{=} listelem elem)}, ie.@: the second\n"
1168 "argument is one of the given @var{elem} parameters.\n"
1171 "(lset-adjoin eqv? '(1 2 3) 4 1 5) @result{} (5 4 1 2 3)\n"
1173 #define FUNC_NAME s_scm_srfi1_lset_adjoin
1175 scm_t_trampoline_2 equal_tramp
;
1178 equal_tramp
= scm_trampoline_2 (equal
);
1179 SCM_ASSERT (equal_tramp
, equal
, SCM_ARG1
, FUNC_NAME
);
1180 SCM_VALIDATE_REST_ARGUMENT (rest
);
1182 /* It's not clear if duplicates among the `rest' elements are meant to be
1183 cast out. The spec says `=' is called as (= list-elem rest-elem),
1184 suggesting perhaps not, but the reference implementation shows the
1185 "list" at each stage as including those "rest" elements already added.
1186 The latter corresponds to what's described for lset-union, so that's
1187 what's done here. */
1189 for ( ; scm_is_pair (rest
); rest
= SCM_CDR (rest
))
1191 elem
= SCM_CAR (rest
);
1193 for (l
= lst
; scm_is_pair (l
); l
= SCM_CDR (l
))
1194 if (scm_is_true (equal_tramp (equal
, SCM_CAR (l
), elem
)))
1195 goto next_elem
; /* elem already in lst, don't add */
1197 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(l
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1199 /* elem is not equal to anything already in lst, add it */
1200 lst
= scm_cons (elem
, lst
);
1211 SCM_DEFINE (scm_srfi1_lset_difference_x
, "lset-difference!", 2, 0, 1,
1212 (SCM equal
, SCM lst
, SCM rest
),
1213 "Return @var{lst} with any elements in the lists in @var{rest}\n"
1214 "removed (ie.@: subtracted). For only one @var{lst} argument,\n"
1215 "just that list is returned.\n"
1217 "The given @var{equal} procedure is used for comparing elements,\n"
1218 "called as @code{(@var{equal} elem1 elemN)}. The first argument\n"
1219 "is from @var{lst} and the second from one of the subsequent\n"
1220 "lists. But exactly which calls are made and in what order is\n"
1224 "(lset-difference! eqv? (list 'x 'y)) @result{} (x y)\n"
1225 "(lset-difference! eqv? (list 1 2 3) '(3 1)) @result{} (2)\n"
1226 "(lset-difference! eqv? (list 1 2 3) '(3) '(2)) @result{} (1)\n"
1229 "@code{lset-difference!} may modify @var{lst} to form its\n"
1231 #define FUNC_NAME s_scm_srfi1_lset_difference_x
1233 scm_t_trampoline_2 equal_tramp
= scm_trampoline_2 (equal
);
1234 SCM ret
, *pos
, elem
, r
, b
;
1237 SCM_ASSERT (equal_tramp
, equal
, SCM_ARG1
, FUNC_NAME
);
1238 SCM_VALIDATE_REST_ARGUMENT (rest
);
1242 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1244 elem
= SCM_CAR (lst
);
1246 for (r
= rest
, argnum
= SCM_ARG3
;
1248 r
= SCM_CDR (r
), argnum
++)
1250 for (b
= SCM_CAR (r
); scm_is_pair (b
); b
= SCM_CDR (b
))
1251 if (scm_is_true (equal_tramp (equal
, elem
, SCM_CAR (b
))))
1252 goto next_elem
; /* equal to elem, so drop that elem */
1254 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (b
), b
, argnum
, FUNC_NAME
,"list");
1257 /* elem not equal to anything in later lists, so keep it */
1259 pos
= SCM_CDRLOC (lst
);
1264 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1272 /* Typechecking for multi-argument MAP and FOR-EACH.
1274 Verify that each element of the vector ARGV, except for the first,
1275 is a list and return minimum length. Attribute errors to WHO,
1276 and claim that the i'th element of ARGV is WHO's i+2'th argument. */
1278 check_map_args (SCM argv
,
1288 for (i
= SCM_SIMPLE_VECTOR_LENGTH (argv
) - 1; i
>= 1; i
--)
1291 elt
= SCM_SIMPLE_VECTOR_REF (argv
, i
);
1293 if (!(scm_is_null (elt
) || scm_is_pair (elt
)))
1294 goto check_map_error
;
1296 elt_len
= srfi1_ilength (elt
);
1298 goto check_map_error
;
1300 if (len
< 0 || (elt_len
>= 0 && elt_len
< len
))
1310 scm_apply_generic (gf
, scm_cons (proc
, args
));
1312 scm_wrong_type_arg (who
, i
+ 2, elt
);
1315 scm_remember_upto_here_1 (argv
);
1320 SCM_GPROC (s_srfi1_map
, "map", 2, 0, 1, scm_srfi1_map
, g_srfi1_map
);
1322 /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s)
1323 sequentially, starting with the first element(s). This is used in
1324 the Scheme procedure `map-in-order', which guarantees sequential
1325 behaviour, is implemented using scm_map. If the behaviour changes,
1326 we need to update `map-in-order'.
1330 scm_srfi1_map (SCM proc
, SCM arg1
, SCM args
)
1331 #define FUNC_NAME s_srfi1_map
1337 len
= srfi1_ilength (arg1
);
1338 SCM_GASSERTn ((scm_is_null (arg1
) || scm_is_pair (arg1
)) && len
>= -1,
1340 scm_cons2 (proc
, arg1
, args
), SCM_ARG2
, s_srfi1_map
);
1341 SCM_VALIDATE_REST_ARGUMENT (args
);
1342 if (scm_is_null (args
))
1344 scm_t_trampoline_1 call
= scm_trampoline_1 (proc
);
1345 SCM_GASSERT2 (call
, g_srfi1_map
, proc
, arg1
, SCM_ARG1
, s_srfi1_map
);
1346 SCM_GASSERT2 (len
>= 0, g_srfi1_map
, proc
, arg1
, SCM_ARG2
, s_srfi1_map
);
1347 while (SCM_NIMP (arg1
))
1349 *pres
= scm_list_1 (call (proc
, SCM_CAR (arg1
)));
1350 pres
= SCM_CDRLOC (*pres
);
1351 arg1
= SCM_CDR (arg1
);
1355 if (scm_is_null (SCM_CDR (args
)))
1357 SCM arg2
= SCM_CAR (args
);
1358 int len2
= srfi1_ilength (arg2
);
1359 scm_t_trampoline_2 call
= scm_trampoline_2 (proc
);
1360 SCM_GASSERTn (call
, g_srfi1_map
,
1361 scm_cons2 (proc
, arg1
, args
), SCM_ARG1
, s_srfi1_map
);
1362 if (len
< 0 || (len2
>= 0 && len2
< len
))
1364 SCM_GASSERTn ((scm_is_null (arg2
) || scm_is_pair (arg2
))
1365 && len
>= 0 && len2
>= -1,
1367 scm_cons2 (proc
, arg1
, args
),
1368 len2
>= 0 ? SCM_ARG2
: SCM_ARG3
,
1372 *pres
= scm_list_1 (call (proc
, SCM_CAR (arg1
), SCM_CAR (arg2
)));
1373 pres
= SCM_CDRLOC (*pres
);
1374 arg1
= SCM_CDR (arg1
);
1375 arg2
= SCM_CDR (arg2
);
1380 args
= scm_vector (arg1
= scm_cons (arg1
, args
));
1381 len
= check_map_args (args
, len
, g_srfi1_map
, proc
, arg1
, s_srfi1_map
);
1385 for (i
= SCM_SIMPLE_VECTOR_LENGTH (args
) - 1; i
>= 0; i
--)
1387 SCM elt
= SCM_SIMPLE_VECTOR_REF (args
, i
);
1388 arg1
= scm_cons (SCM_CAR (elt
), arg1
);
1389 SCM_SIMPLE_VECTOR_SET (args
, i
, SCM_CDR (elt
));
1391 *pres
= scm_list_1 (scm_apply (proc
, arg1
, SCM_EOL
));
1392 pres
= SCM_CDRLOC (*pres
);
1399 SCM_REGISTER_PROC (s_srfi1_map_in_order
, "map-in-order", 2, 0, 1, scm_srfi1_map
);
1401 SCM_GPROC (s_srfi1_for_each
, "for-each", 2, 0, 1, scm_srfi1_for_each
, g_srfi1_for_each
);
1404 scm_srfi1_for_each (SCM proc
, SCM arg1
, SCM args
)
1405 #define FUNC_NAME s_srfi1_for_each
1408 len
= srfi1_ilength (arg1
);
1409 SCM_GASSERTn ((scm_is_null (arg1
) || scm_is_pair (arg1
)) && len
>= -1,
1410 g_srfi1_for_each
, scm_cons2 (proc
, arg1
, args
),
1411 SCM_ARG2
, s_srfi1_for_each
);
1412 SCM_VALIDATE_REST_ARGUMENT (args
);
1413 if (scm_is_null (args
))
1415 scm_t_trampoline_1 call
= scm_trampoline_1 (proc
);
1416 SCM_GASSERT2 (call
, g_srfi1_for_each
, proc
, arg1
,
1417 SCM_ARG1
, s_srfi1_for_each
);
1418 SCM_GASSERT2 (len
>= 0, g_srfi1_for_each
, proc
, arg1
,
1419 SCM_ARG2
, s_srfi1_map
);
1420 while (SCM_NIMP (arg1
))
1422 call (proc
, SCM_CAR (arg1
));
1423 arg1
= SCM_CDR (arg1
);
1425 return SCM_UNSPECIFIED
;
1427 if (scm_is_null (SCM_CDR (args
)))
1429 SCM arg2
= SCM_CAR (args
);
1430 int len2
= srfi1_ilength (arg2
);
1431 scm_t_trampoline_2 call
= scm_trampoline_2 (proc
);
1432 SCM_GASSERTn (call
, g_srfi1_for_each
,
1433 scm_cons2 (proc
, arg1
, args
), SCM_ARG1
, s_srfi1_for_each
);
1434 if (len
< 0 || (len2
>= 0 && len2
< len
))
1436 SCM_GASSERTn ((scm_is_null (arg2
) || scm_is_pair (arg2
))
1437 && len
>= 0 && len2
>= -1,
1439 scm_cons2 (proc
, arg1
, args
),
1440 len2
>= 0 ? SCM_ARG2
: SCM_ARG3
,
1444 call (proc
, SCM_CAR (arg1
), SCM_CAR (arg2
));
1445 arg1
= SCM_CDR (arg1
);
1446 arg2
= SCM_CDR (arg2
);
1449 return SCM_UNSPECIFIED
;
1451 args
= scm_vector (arg1
= scm_cons (arg1
, args
));
1452 len
= check_map_args (args
, len
, g_srfi1_for_each
, proc
, arg1
,
1457 for (i
= SCM_SIMPLE_VECTOR_LENGTH (args
) - 1; i
>= 0; i
--)
1459 SCM elt
= SCM_SIMPLE_VECTOR_REF (args
, i
);
1460 arg1
= scm_cons (SCM_CAR (elt
), arg1
);
1461 SCM_SIMPLE_VECTOR_SET (args
, i
, SCM_CDR (elt
));
1463 scm_apply (proc
, arg1
, SCM_EOL
);
1466 return SCM_UNSPECIFIED
;
1471 SCM_DEFINE (scm_srfi1_member
, "member", 2, 1, 0,
1472 (SCM x
, SCM lst
, SCM pred
),
1473 "Return the first sublist of @var{lst} whose @sc{car} is equal\n"
1474 "to @var{x}. If @var{x} does not appear in @var{lst}, return\n"
1477 "Equality is determined by @code{equal?}, or by the equality\n"
1478 "predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n"
1479 "elem)}, ie.@: with the given @var{x} first, so for example to\n"
1480 "find the first element greater than 5,\n"
1483 "(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n"
1486 "This version of @code{member} extends the core @code{member} by\n"
1487 "accepting an equality predicate.")
1488 #define FUNC_NAME s_scm_srfi1_member
1490 scm_t_trampoline_2 equal_p
;
1491 SCM_VALIDATE_LIST (2, lst
);
1492 if (SCM_UNBNDP (pred
))
1493 equal_p
= equal_trampoline
;
1496 equal_p
= scm_trampoline_2 (pred
);
1497 SCM_ASSERT (equal_p
, pred
, 3, FUNC_NAME
);
1499 for (; !SCM_NULL_OR_NIL_P (lst
); lst
= SCM_CDR (lst
))
1501 if (scm_is_true (equal_p (pred
, x
, SCM_CAR (lst
))))
1508 SCM_DEFINE (scm_srfi1_assoc
, "assoc", 2, 1, 0,
1509 (SCM key
, SCM alist
, SCM pred
),
1510 "Behaves like @code{assq} but uses third argument @var{pred?}\n"
1511 "for key comparison. If @var{pred?} is not supplied,\n"
1512 "@code{equal?} is used. (Extended from R5RS.)\n")
1513 #define FUNC_NAME s_scm_srfi1_assoc
1516 scm_t_trampoline_2 equal_p
;
1517 if (SCM_UNBNDP (pred
))
1518 equal_p
= equal_trampoline
;
1521 equal_p
= scm_trampoline_2 (pred
);
1522 SCM_ASSERT (equal_p
, pred
, 3, FUNC_NAME
);
1524 for(; scm_is_pair (ls
); ls
= SCM_CDR (ls
))
1526 SCM tmp
= SCM_CAR (ls
);
1527 SCM_ASSERT_TYPE (scm_is_pair (tmp
), alist
, SCM_ARG2
, FUNC_NAME
,
1528 "association list");
1529 if (scm_is_true (equal_p (pred
, SCM_CAR (tmp
), key
)))
1532 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls
), alist
, SCM_ARG2
, FUNC_NAME
,
1533 "association list");
1539 SCM_DEFINE (scm_srfi1_ninth
, "ninth", 1, 0, 0,
1541 "Return the ninth element of @var{lst}.")
1542 #define FUNC_NAME s_scm_srfi1_ninth
1544 return scm_list_ref (lst
, scm_from_int (8));
1549 SCM_DEFINE (scm_srfi1_not_pair_p
, "not-pair?", 1, 0, 0,
1551 "Return @code{#t} is @var{obj} is not a pair, @code{#f}\n"
1554 "This is shorthand notation @code{(not (pair? @var{obj}))} and\n"
1555 "is supposed to be used for end-of-list checking in contexts\n"
1556 "where dotted lists are allowed.")
1557 #define FUNC_NAME s_scm_srfi1_not_pair_p
1559 return scm_from_bool (! scm_is_pair (obj
));
1564 SCM_DEFINE (scm_srfi1_partition
, "partition", 2, 0, 0,
1565 (SCM pred
, SCM list
),
1566 "Partition the elements of @var{list} with predicate @var{pred}.\n"
1567 "Return two values: the list of elements satifying @var{pred} and\n"
1568 "the list of elements @emph{not} satisfying @var{pred}. The order\n"
1569 "of the output lists follows the order of @var{list}. @var{list}\n"
1570 "is not mutated. One of the output lists may share memory with @var{list}.\n")
1571 #define FUNC_NAME s_scm_srfi1_partition
1573 /* In this implementation, the output lists don't share memory with
1574 list, because it's probably not worth the effort. */
1575 scm_t_trampoline_1 call
= scm_trampoline_1(pred
);
1576 SCM kept
= scm_cons(SCM_EOL
, SCM_EOL
);
1577 SCM kept_tail
= kept
;
1578 SCM dropped
= scm_cons(SCM_EOL
, SCM_EOL
);
1579 SCM dropped_tail
= dropped
;
1581 SCM_ASSERT(call
, pred
, 2, FUNC_NAME
);
1583 for (; !SCM_NULL_OR_NIL_P (list
); list
= SCM_CDR(list
)) {
1584 SCM elt
= SCM_CAR(list
);
1585 SCM new_tail
= scm_cons(SCM_CAR(list
), SCM_EOL
);
1586 if (scm_is_true (call (pred
, elt
))) {
1587 SCM_SETCDR(kept_tail
, new_tail
);
1588 kept_tail
= new_tail
;
1591 SCM_SETCDR(dropped_tail
, new_tail
);
1592 dropped_tail
= new_tail
;
1595 /* re-use the initial conses for the values list */
1596 SCM_SETCAR(kept
, SCM_CDR(kept
));
1597 SCM_SETCDR(kept
, dropped
);
1598 SCM_SETCAR(dropped
, SCM_CDR(dropped
));
1599 SCM_SETCDR(dropped
, SCM_EOL
);
1600 return scm_values(kept
);
1605 SCM_DEFINE (scm_srfi1_partition_x
, "partition!", 2, 0, 0,
1606 (SCM pred
, SCM lst
),
1607 "Split @var{lst} into those elements which do and don't satisfy\n"
1608 "the predicate @var{pred}.\n"
1610 "The return is two values (@pxref{Multiple Values}), the first\n"
1611 "being a list of all elements from @var{lst} which satisfy\n"
1612 "@var{pred}, the second a list of those which do not.\n"
1614 "The elements in the result lists are in the same order as in\n"
1615 "@var{lst} but the order in which the calls @code{(@var{pred}\n"
1616 "elem)} are made on the list elements is unspecified.\n"
1618 "@var{lst} may be modified to construct the return lists.")
1619 #define FUNC_NAME s_scm_srfi1_partition_x
1621 SCM tlst
, flst
, *tp
, *fp
;
1622 scm_t_trampoline_1 pred_tramp
;
1624 pred_tramp
= scm_trampoline_1 (pred
);
1625 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
1627 /* tlst and flst are the lists of true and false elements. tp and fp are
1628 where to store to append to them, initially &tlst and &flst, then
1629 SCM_CDRLOC of the last pair in the respective lists. */
1636 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1638 if (scm_is_true (pred_tramp (pred
, SCM_CAR (lst
))))
1641 tp
= SCM_CDRLOC (lst
);
1646 fp
= SCM_CDRLOC (lst
);
1650 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1652 /* terminate whichever didn't get the last element(s) */
1656 return scm_values (scm_list_2 (tlst
, flst
));
1661 SCM_DEFINE (scm_srfi1_reduce
, "reduce", 3, 0, 0,
1662 (SCM proc
, SCM def
, SCM lst
),
1663 "@code{reduce} is a variant of @code{fold}, where the first call\n"
1664 "to @var{proc} is on two elements from @var{lst}, rather than\n"
1665 "one element and a given initial value.\n"
1667 "If @var{lst} is empty, @code{reduce} returns @var{def} (this is\n"
1668 "the only use for @var{def}). If @var{lst} has just one element\n"
1669 "then that's the return value. Otherwise @var{proc} is called\n"
1670 "on the elements of @var{lst}.\n"
1672 "Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1673 "@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1674 "second and subsequent elements of @var{lst}), and\n"
1675 "@var{previous} is the return from the previous call to\n"
1676 "@var{proc}. The first element of @var{lst} is the\n"
1677 "@var{previous} for the first call to @var{proc}.\n"
1679 "For example, the following adds a list of numbers, the calls\n"
1680 "made to @code{+} are shown. (Of course @code{+} accepts\n"
1681 "multiple arguments and can add a list directly, with\n"
1685 "(reduce + 0 '(5 6 7)) @result{} 18\n"
1687 "(+ 6 5) @result{} 11\n"
1688 "(+ 7 11) @result{} 18\n"
1691 "@code{reduce} can be used instead of @code{fold} where the\n"
1692 "@var{init} value is an ``identity'', meaning a value which\n"
1693 "under @var{proc} doesn't change the result, in this case 0 is\n"
1694 "an identity since @code{(+ 5 0)} is just 5. @code{reduce}\n"
1695 "avoids that unnecessary call.")
1696 #define FUNC_NAME s_scm_srfi1_reduce
1698 scm_t_trampoline_2 proc_tramp
= scm_trampoline_2 (proc
);
1701 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG1
, FUNC_NAME
);
1703 ret
= def
; /* if lst is empty */
1704 if (scm_is_pair (lst
))
1706 ret
= SCM_CAR (lst
); /* if lst has one element */
1708 for (lst
= SCM_CDR (lst
); scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1709 ret
= proc_tramp (proc
, SCM_CAR (lst
), ret
);
1712 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG3
, FUNC_NAME
, "list");
1718 SCM_DEFINE (scm_srfi1_reduce_right
, "reduce-right", 3, 0, 0,
1719 (SCM proc
, SCM def
, SCM lst
),
1720 "@code{reduce-right} is a variant of @code{fold-right}, where\n"
1721 "the first call to @var{proc} is on two elements from @var{lst},\n"
1722 "rather than one element and a given initial value.\n"
1724 "If @var{lst} is empty, @code{reduce-right} returns @var{def}\n"
1725 "(this is the only use for @var{def}). If @var{lst} has just\n"
1726 "one element then that's the return value. Otherwise @var{proc}\n"
1727 "is called on the elements of @var{lst}.\n"
1729 "Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1730 "@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1731 "second last and then working back to the first element of\n"
1732 "@var{lst}), and @var{previous} is the return from the previous\n"
1733 "call to @var{proc}. The last element of @var{lst} is the\n"
1734 "@var{previous} for the first call to @var{proc}.\n"
1736 "For example, the following adds a list of numbers, the calls\n"
1737 "made to @code{+} are shown. (Of course @code{+} accepts\n"
1738 "multiple arguments and can add a list directly, with\n"
1742 "(reduce-right + 0 '(5 6 7)) @result{} 18\n"
1744 "(+ 6 7) @result{} 13\n"
1745 "(+ 5 13) @result{} 18\n"
1748 "@code{reduce-right} can be used instead of @code{fold-right}\n"
1749 "where the @var{init} value is an ``identity'', meaning a value\n"
1750 "which under @var{proc} doesn't change the result, in this case\n"
1751 "0 is an identity since @code{(+ 7 0)} is just 5.\n"
1752 "@code{reduce-right} avoids that unnecessary call.\n"
1754 "@code{reduce} should be preferred over @code{reduce-right} if\n"
1755 "the order of processing doesn't matter, or can be arranged\n"
1756 "either way, since @code{reduce} is a little more efficient.")
1757 #define FUNC_NAME s_scm_srfi1_reduce_right
1759 /* To work backwards across a list requires either repeatedly traversing
1760 to get each previous element, or using some memory for a reversed or
1761 random-access form. Repeated traversal might not be too terrible, but
1762 is of course quadratic complexity and hence to be avoided in case LST
1763 is long. A vector is preferred over a reversed list since it's more
1764 compact and is less work for the gc to collect. */
1766 scm_t_trampoline_2 proc_tramp
= scm_trampoline_2 (proc
);
1770 SCM_ASSERT (proc_tramp
, proc
, SCM_ARG1
, FUNC_NAME
);
1772 if (SCM_NULL_OR_NIL_P (lst
))
1775 vec
= scm_vector (lst
);
1776 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
1778 ret
= SCM_SIMPLE_VECTOR_REF (vec
, len
-1);
1779 for (i
= len
-2; i
>= 0; i
--)
1780 ret
= proc_tramp (proc
, SCM_SIMPLE_VECTOR_REF (vec
, i
), ret
);
1787 SCM_DEFINE (scm_srfi1_remove
, "remove", 2, 0, 0,
1788 (SCM pred
, SCM list
),
1789 "Return a list containing all elements from @var{lst} which do\n"
1790 "not satisfy the predicate @var{pred}. The elements in the\n"
1791 "result list have the same order as in @var{lst}. The order in\n"
1792 "which @var{pred} is applied to the list elements is not\n"
1794 #define FUNC_NAME s_scm_srfi1_remove
1796 scm_t_trampoline_1 call
= scm_trampoline_1 (pred
);
1800 SCM_ASSERT (call
, pred
, 1, FUNC_NAME
);
1801 SCM_VALIDATE_LIST (2, list
);
1803 for (prev
= &res
, walk
= list
;
1805 walk
= SCM_CDR (walk
))
1807 if (scm_is_false (call (pred
, SCM_CAR (walk
))))
1809 *prev
= scm_cons (SCM_CAR (walk
), SCM_EOL
);
1810 prev
= SCM_CDRLOC (*prev
);
1819 SCM_DEFINE (scm_srfi1_remove_x
, "remove!", 2, 0, 0,
1820 (SCM pred
, SCM list
),
1821 "Return a list containing all elements from @var{list} which do\n"
1822 "not satisfy the predicate @var{pred}. The elements in the\n"
1823 "result list have the same order as in @var{list}. The order in\n"
1824 "which @var{pred} is applied to the list elements is not\n"
1825 "specified. @var{list} may be modified to build the return\n"
1827 #define FUNC_NAME s_scm_srfi1_remove_x
1829 scm_t_trampoline_1 call
= scm_trampoline_1 (pred
);
1832 SCM_ASSERT (call
, pred
, 1, FUNC_NAME
);
1833 SCM_VALIDATE_LIST (2, list
);
1835 for (prev
= &list
, walk
= list
;
1837 walk
= SCM_CDR (walk
))
1839 if (scm_is_false (call (pred
, SCM_CAR (walk
))))
1840 prev
= SCM_CDRLOC (walk
);
1842 *prev
= SCM_CDR (walk
);
1850 SCM_DEFINE (scm_srfi1_seventh
, "seventh", 1, 0, 0,
1852 "Return the seventh element of @var{lst}.")
1853 #define FUNC_NAME s_scm_srfi1_seventh
1855 return scm_list_ref (lst
, scm_from_int (6));
1860 SCM_DEFINE (scm_srfi1_sixth
, "sixth", 1, 0, 0,
1862 "Return the sixth element of @var{lst}.")
1863 #define FUNC_NAME s_scm_srfi1_sixth
1865 return scm_list_ref (lst
, scm_from_int (5));
1870 SCM_DEFINE (scm_srfi1_span
, "span", 2, 0, 0,
1871 (SCM pred
, SCM lst
),
1872 "Return two values, the longest initial prefix of @var{lst}\n"
1873 "whose elements all satisfy the predicate @var{pred}, and the\n"
1874 "remainder of @var{lst}.")
1875 #define FUNC_NAME s_scm_srfi1_span
1877 scm_t_trampoline_1 pred_tramp
;
1880 pred_tramp
= scm_trampoline_1 (pred
);
1881 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
1885 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1887 SCM elem
= SCM_CAR (lst
);
1888 if (scm_is_false (pred_tramp (pred
, elem
)))
1891 /* want this elem, tack it onto the end of ret */
1892 *p
= scm_cons (elem
, SCM_EOL
);
1893 p
= SCM_CDRLOC (*p
);
1895 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1898 return scm_values (scm_list_2 (ret
, lst
));
1903 SCM_DEFINE (scm_srfi1_span_x
, "span!", 2, 0, 0,
1904 (SCM pred
, SCM lst
),
1905 "Return two values, the longest initial prefix of @var{lst}\n"
1906 "whose elements all satisfy the predicate @var{pred}, and the\n"
1907 "remainder of @var{lst}. @var{lst} may be modified to form the\n"
1909 #define FUNC_NAME s_scm_srfi1_span_x
1912 scm_t_trampoline_1 pred_tramp
;
1914 pred_tramp
= scm_trampoline_1 (pred
);
1915 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
1918 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
1920 if (scm_is_false (pred_tramp (pred
, SCM_CAR (upto
))))
1923 /* want this element */
1924 p
= SCM_CDRLOC (upto
);
1926 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1930 return scm_values (scm_list_2 (lst
, upto
));
1935 SCM_DEFINE (scm_srfi1_split_at
, "split-at", 2, 0, 0,
1937 "Return two values (multiple values), being a list of the\n"
1938 "elements before index @var{n} in @var{lst}, and a list of those\n"
1940 #define FUNC_NAME s_scm_srfi1_split_at
1943 /* pre is a list of elements before the i split point, loc is the CDRLOC
1944 of the last cell, ie. where to store to append to it */
1948 for (nn
= scm_to_size_t (n
); nn
!= 0; nn
--)
1950 SCM_VALIDATE_CONS (SCM_ARG1
, lst
);
1952 *loc
= scm_cons (SCM_CAR (lst
), SCM_EOL
);
1953 loc
= SCM_CDRLOC (*loc
);
1956 return scm_values (scm_list_2 (pre
, lst
));
1961 SCM_DEFINE (scm_srfi1_split_at_x
, "split-at!", 2, 0, 0,
1963 "Return two values (multiple values), being a list of the\n"
1964 "elements before index @var{n} in @var{lst}, and a list of those\n"
1965 "after. @var{lst} is modified to form those values.")
1966 #define FUNC_NAME s_scm_srfi1_split_at
1972 for (nn
= scm_to_size_t (n
); nn
!= 0; nn
--)
1974 SCM_VALIDATE_CONS (SCM_ARG1
, upto
);
1976 loc
= SCM_CDRLOC (upto
);
1977 upto
= SCM_CDR (upto
);
1981 return scm_values (scm_list_2 (lst
, upto
));
1986 SCM_DEFINE (scm_srfi1_take_x
, "take!", 2, 0, 0,
1988 "Return a list containing the first @var{n} elements of\n"
1990 #define FUNC_NAME s_scm_srfi1_take_x
1995 nn
= scm_to_signed_integer (n
, 0, LONG_MAX
);
1999 pos
= scm_list_tail (lst
, scm_from_long (nn
- 1));
2001 /* Must have at least one cell left, mustn't have reached the end of an
2002 n-1 element list. SCM_VALIDATE_CONS here gives the same error as
2003 scm_list_tail does on say an n-2 element list, though perhaps a range
2004 error would make more sense (for both). */
2005 SCM_VALIDATE_CONS (SCM_ARG1
, pos
);
2007 SCM_SETCDR (pos
, SCM_EOL
);
2013 SCM_DEFINE (scm_srfi1_take_right
, "take-right", 2, 0, 0,
2015 "Return the a list containing the @var{n} last elements of\n"
2017 #define FUNC_NAME s_scm_srfi1_take_right
2019 SCM tail
= scm_list_tail (lst
, n
);
2020 while (scm_is_pair (tail
))
2022 lst
= SCM_CDR (lst
);
2023 tail
= SCM_CDR (tail
);
2025 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
2031 SCM_DEFINE (scm_srfi1_take_while
, "take-while", 2, 0, 0,
2032 (SCM pred
, SCM lst
),
2033 "Return a new list which is the longest initial prefix of\n"
2034 "@var{lst} whose elements all satisfy the predicate @var{pred}.")
2035 #define FUNC_NAME s_scm_srfi1_take_while
2037 scm_t_trampoline_1 pred_tramp
;
2040 pred_tramp
= scm_trampoline_1 (pred
);
2041 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
2045 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
2047 SCM elem
= SCM_CAR (lst
);
2048 if (scm_is_false (pred_tramp (pred
, elem
)))
2051 /* want this elem, tack it onto the end of ret */
2052 *p
= scm_cons (elem
, SCM_EOL
);
2053 p
= SCM_CDRLOC (*p
);
2055 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
2063 SCM_DEFINE (scm_srfi1_take_while_x
, "take-while!", 2, 0, 0,
2064 (SCM pred
, SCM lst
),
2065 "Return the longest initial prefix of @var{lst} whose elements\n"
2066 "all satisfy the predicate @var{pred}. @var{lst} may be\n"
2067 "modified to form the return.")
2068 #define FUNC_NAME s_scm_srfi1_take_while_x
2071 scm_t_trampoline_1 pred_tramp
;
2073 pred_tramp
= scm_trampoline_1 (pred
);
2074 SCM_ASSERT (pred_tramp
, pred
, SCM_ARG1
, FUNC_NAME
);
2077 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
2079 if (scm_is_false (pred_tramp (pred
, SCM_CAR (upto
))))
2082 /* want this element */
2083 p
= SCM_CDRLOC (upto
);
2085 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
2094 SCM_DEFINE (scm_srfi1_tenth
, "tenth", 1, 0, 0,
2096 "Return the tenth element of @var{lst}.")
2097 #define FUNC_NAME s_scm_srfi1_tenth
2099 return scm_list_ref (lst
, scm_from_int (9));
2104 SCM_DEFINE (scm_srfi1_xcons
, "xcons", 2, 0, 0,
2106 "Like @code{cons}, but with interchanged arguments. Useful\n"
2107 "mostly when passed to higher-order procedures.")
2108 #define FUNC_NAME s_scm_srfi1_xcons
2110 return scm_cons (a
, d
);
2116 scm_init_srfi_1 (void)
2118 SCM the_root_module
= scm_lookup_closure_module (SCM_BOOL_F
);
2119 #ifndef SCM_MAGIC_SNARFER
2120 #include "srfi/srfi-1.x"
2122 scm_c_extend_primitive_generic
2123 (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module
, "map")),
2124 SCM_VARIABLE_REF (scm_c_lookup ("map")));
2125 scm_c_extend_primitive_generic
2126 (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module
, "for-each")),
2127 SCM_VARIABLE_REF (scm_c_lookup ("for-each")));
2130 /* End of srfi-1.c. */