1 /* srfi-1.c --- SRFI-1 procedures for Guile
3 * Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006, 2008, 2009
4 * Free Software Foundation, Inc.
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public License
8 * as published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful, but
12 * 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
27 #include <libguile/lang.h>
31 /* The intent of this file is to gradually replace those Scheme
32 * procedures in srfi-1.scm which extends core primitive procedures,
33 * so that using srfi-1 won't have performance penalties.
35 * Please feel free to contribute any new replacements!
39 srfi1_ilength (SCM sx
)
46 if (SCM_NULL_OR_NIL_P(hare
)) return i
;
47 if (!scm_is_pair (hare
)) return -2;
50 if (SCM_NULL_OR_NIL_P(hare
)) return i
;
51 if (!scm_is_pair (hare
)) return -2;
54 /* For every two steps the hare takes, the tortoise takes one. */
55 tortoise
= SCM_CDR(tortoise
);
57 while (! scm_is_eq (hare
, tortoise
));
59 /* If the tortoise ever catches the hare, then the list must contain
65 equal_trampoline (SCM proc
, SCM arg1
, SCM arg2
)
67 return scm_equal_p (arg1
, arg2
);
70 /* list_copy_part() copies the first COUNT cells of LST, puts the result at
71 *dst, and returns the SCM_CDRLOC of the last cell in that new list.
73 This function is designed to be careful about LST possibly having changed
74 in between the caller deciding what to copy, and the copy actually being
75 done here. The COUNT ensures we terminate if LST has become circular,
76 SCM_VALIDATE_CONS guards against a cdr in the list changed to some
81 list_copy_part (SCM lst
, int count
, SCM
*dst
)
82 #define FUNC_NAME "list_copy_part"
85 for ( ; count
> 0; count
--)
87 SCM_VALIDATE_CONS (SCM_ARGn
, lst
);
88 c
= scm_cons (SCM_CAR (lst
), SCM_EOL
);
98 SCM_DEFINE (scm_srfi1_alist_copy
, "alist-copy", 1, 0, 0,
100 "Return a copy of @var{alist}, copying both the pairs comprising\n"
101 "the list and those making the associations.")
102 #define FUNC_NAME s_scm_srfi1_alist_copy
104 SCM ret
, *p
, elem
, c
;
106 /* ret is the list to return. p is where to append to it, initially &ret
107 then SCM_CDRLOC of the last pair. */
111 for ( ; scm_is_pair (alist
); alist
= SCM_CDR (alist
))
113 elem
= SCM_CAR (alist
);
115 /* each element of alist must be a pair */
116 SCM_ASSERT_TYPE (scm_is_pair (elem
), alist
, SCM_ARG1
, FUNC_NAME
,
119 c
= scm_cons (scm_cons (SCM_CAR (elem
), SCM_CDR (elem
)), SCM_EOL
);
124 /* alist must be a proper list */
125 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (alist
), alist
, SCM_ARG1
, FUNC_NAME
,
133 SCM_DEFINE (scm_srfi1_append_reverse
, "append-reverse", 2, 0, 0,
134 (SCM revhead
, SCM tail
),
135 "Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
136 "result. This is equivalent to @code{(append (reverse\n"
137 "@var{rev-head}) @var{tail})}, but its implementation is more\n"
141 "(append-reverse '(1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
143 #define FUNC_NAME s_scm_srfi1_append_reverse
145 while (scm_is_pair (revhead
))
147 /* copy first element of revhead onto front of tail */
148 tail
= scm_cons (SCM_CAR (revhead
), tail
);
149 revhead
= SCM_CDR (revhead
);
151 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead
), revhead
, SCM_ARG1
, FUNC_NAME
,
158 SCM_DEFINE (scm_srfi1_append_reverse_x
, "append-reverse!", 2, 0, 0,
159 (SCM revhead
, SCM tail
),
160 "Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
161 "result. This is equivalent to @code{(append! (reverse!\n"
162 "@var{rev-head}) @var{tail})}, but its implementation is more\n"
166 "(append-reverse! (list 1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
169 "@var{rev-head} may be modified in order to produce the result.")
170 #define FUNC_NAME s_scm_srfi1_append_reverse_x
174 while (scm_is_pair (revhead
))
176 /* take the first cons cell from revhead */
178 revhead
= SCM_CDR (revhead
);
180 /* make it the new start of tail, appending the previous */
181 SCM_SETCDR (newtail
, tail
);
184 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead
), revhead
, SCM_ARG1
, FUNC_NAME
,
191 SCM_DEFINE (scm_srfi1_break
, "break", 2, 0, 0,
193 "Return two values, the longest initial prefix of @var{lst}\n"
194 "whose elements all fail the predicate @var{pred}, and the\n"
195 "remainder of @var{lst}.\n"
197 "Note that the name @code{break} conflicts with the @code{break}\n"
198 "binding established by @code{while}. Applications wanting to\n"
199 "use @code{break} from within a @code{while} loop will need to\n"
200 "make a new define under a different name.")
201 #define FUNC_NAME s_scm_srfi1_break
205 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
209 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
211 SCM elem
= SCM_CAR (lst
);
212 if (scm_is_true (scm_call_1 (pred
, elem
)))
215 /* want this elem, tack it onto the end of ret */
216 *p
= scm_cons (elem
, SCM_EOL
);
219 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
222 return scm_values (scm_list_2 (ret
, lst
));
227 SCM_DEFINE (scm_srfi1_break_x
, "break!", 2, 0, 0,
229 "Return two values, the longest initial prefix of @var{lst}\n"
230 "whose elements all fail the predicate @var{pred}, and the\n"
231 "remainder of @var{lst}. @var{lst} may be modified to form the\n"
233 #define FUNC_NAME s_scm_srfi1_break_x
237 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
240 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
242 if (scm_is_true (scm_call_1 (pred
, SCM_CAR (upto
))))
245 /* want this element */
246 p
= SCM_CDRLOC (upto
);
248 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
252 return scm_values (scm_list_2 (lst
, upto
));
257 SCM_DEFINE (scm_srfi1_car_plus_cdr
, "car+cdr", 1, 0, 0,
259 "Return two values, the @sc{car} and the @sc{cdr} of @var{pair}.")
260 #define FUNC_NAME s_scm_srfi1_car_plus_cdr
262 SCM_VALIDATE_CONS (SCM_ARG1
, pair
);
263 return scm_values (scm_list_2 (SCM_CAR (pair
), SCM_CDR (pair
)));
268 SCM_DEFINE (scm_srfi1_concatenate
, "concatenate", 1, 0, 0,
270 "Construct a list by appending all lists in @var{lstlst}.\n"
272 "@code{concatenate} is the same as @code{(apply append\n"
273 "@var{lstlst})}. It exists because some Scheme implementations\n"
274 "have a limit on the number of arguments a function takes, which\n"
275 "the @code{apply} might exceed. In Guile there is no such\n"
277 #define FUNC_NAME s_scm_srfi1_concatenate
279 SCM_VALIDATE_LIST (SCM_ARG1
, lstlst
);
280 return scm_append (lstlst
);
285 SCM_DEFINE (scm_srfi1_concatenate_x
, "concatenate!", 1, 0, 0,
287 "Construct a list by appending all lists in @var{lstlst}. Those\n"
288 "lists may be modified to produce the result.\n"
290 "@code{concatenate!} is the same as @code{(apply append!\n"
291 "@var{lstlst})}. It exists because some Scheme implementations\n"
292 "have a limit on the number of arguments a function takes, which\n"
293 "the @code{apply} might exceed. In Guile there is no such\n"
295 #define FUNC_NAME s_scm_srfi1_concatenate
297 SCM_VALIDATE_LIST (SCM_ARG1
, lstlst
);
298 return scm_append_x (lstlst
);
303 SCM_DEFINE (scm_srfi1_count
, "count", 2, 0, 1,
304 (SCM pred
, SCM list1
, SCM rest
),
305 "Return a count of the number of times @var{pred} returns true\n"
306 "when called on elements from the given lists.\n"
308 "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n"
309 "@var{elem1} @dots{} @var{elemN})}, each element being from the\n"
310 "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n"
311 "with the first element of each list, the second with the second\n"
312 "element from each, and so on.\n"
314 "Counting stops when the end of the shortest list is reached.\n"
315 "At least one list must be non-circular.")
316 #define FUNC_NAME s_scm_srfi1_count
321 SCM_VALIDATE_REST_ARGUMENT (rest
);
325 if (scm_is_null (rest
))
328 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
330 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
331 count
+= scm_is_true (scm_call_1 (pred
, SCM_CAR (list1
)));
333 /* check below that list1 is a proper list, and done */
338 else if (scm_is_pair (rest
) && scm_is_null (SCM_CDR (rest
)))
343 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
345 list2
= SCM_CAR (rest
);
348 if (! scm_is_pair (list1
))
350 if (! scm_is_pair (list2
))
356 count
+= scm_is_true (scm_call_2
357 (pred
, SCM_CAR (list1
), SCM_CAR (list2
)));
358 list1
= SCM_CDR (list1
);
359 list2
= SCM_CDR (list2
);
364 /* three or more lists */
368 /* vec is the list arguments */
369 vec
= scm_vector (scm_cons (list1
, rest
));
370 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
372 /* args is the argument list to pass to pred, same length as vec,
373 re-used for each call */
374 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
378 /* first elem of each list in vec into args, and step those
379 vec entries onto their next element */
380 for (i
= 0, a
= args
, argnum
= 2;
382 i
++, a
= SCM_CDR (a
), argnum
++)
384 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
385 if (! scm_is_pair (lst
))
386 goto check_lst_and_done
;
387 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for pred */
388 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
391 count
+= scm_is_true (scm_apply (pred
, args
, SCM_EOL
));
396 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
397 return scm_from_long (count
);
402 SCM_DEFINE (scm_srfi1_delete
, "delete", 2, 1, 0,
403 (SCM x
, SCM lst
, SCM pred
),
404 "Return a list containing the elements of @var{lst} but with\n"
405 "those equal to @var{x} deleted. The returned elements will be\n"
406 "in the same order as they were in @var{lst}.\n"
408 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
409 "given. An equality call is made just once for each element,\n"
410 "but the order in which the calls are made on the elements is\n"
413 "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
414 "given @var{x} is first. This means for instance elements\n"
415 "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
417 "@var{lst} is not modified, but the returned list might share a\n"
418 "common tail with @var{lst}.")
419 #define FUNC_NAME s_scm_srfi1_delete
421 SCM ret
, *p
, keeplst
;
424 if (SCM_UNBNDP (pred
))
425 return scm_delete (x
, lst
);
427 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG3
, FUNC_NAME
);
429 /* ret is the return list being constructed. p is where to append to it,
430 initially &ret then SCM_CDRLOC of the last pair. lst progresses as
431 elements are considered.
433 Elements to be retained are not immediately copied, instead keeplst is
434 the last pair in lst which is to be retained but not yet copied, count
435 is how many from there are wanted. When there's no more deletions, *p
436 can be set to keeplst to share the remainder of the original lst. (The
437 entire original lst if there's no deletions at all.) */
443 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
445 if (scm_is_true (scm_call_2 (pred
, x
, SCM_CAR (lst
))))
447 /* delete this element, so copy those at keeplst */
448 p
= list_copy_part (keeplst
, count
, p
);
449 keeplst
= SCM_CDR (lst
);
454 /* keep this element */
459 /* final retained elements */
462 /* demand that lst was a proper list */
463 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
470 SCM_DEFINE (scm_srfi1_delete_x
, "delete!", 2, 1, 0,
471 (SCM x
, SCM lst
, SCM pred
),
472 "Return a list containing the elements of @var{lst} but with\n"
473 "those equal to @var{x} deleted. The returned elements will be\n"
474 "in the same order as they were in @var{lst}.\n"
476 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
477 "given. An equality call is made just once for each element,\n"
478 "but the order in which the calls are made on the elements is\n"
481 "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
482 "given @var{x} is first. This means for instance elements\n"
483 "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
485 "@var{lst} may be modified to construct the returned list.")
486 #define FUNC_NAME s_scm_srfi1_delete_x
491 if (SCM_UNBNDP (pred
))
492 return scm_delete_x (x
, lst
);
494 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG3
, FUNC_NAME
);
496 for (prev
= &lst
, walk
= lst
;
498 walk
= SCM_CDR (walk
))
500 if (scm_is_true (scm_call_2 (pred
, x
, SCM_CAR (walk
))))
501 *prev
= SCM_CDR (walk
);
503 prev
= SCM_CDRLOC (walk
);
506 /* demand the input was a proper list */
507 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk
), walk
, SCM_ARG2
, FUNC_NAME
,"list");
513 SCM_DEFINE (scm_srfi1_delete_duplicates
, "delete-duplicates", 1, 1, 0,
515 "Return a list containing the elements of @var{lst} but without\n"
518 "When elements are equal, only the first in @var{lst} is\n"
519 "retained. Equal elements can be anywhere in @var{lst}, they\n"
520 "don't have to be adjacent. The returned list will have the\n"
521 "retained elements in the same order as they were in @var{lst}.\n"
523 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
524 "given. Calls @code{(pred x y)} are made with element @var{x}\n"
525 "being before @var{y} in @var{lst}. A call is made at most once\n"
526 "for each combination, but the sequence of the calls across the\n"
527 "elements is unspecified.\n"
529 "@var{lst} is not modified, but the return might share a common\n"
530 "tail with @var{lst}.\n"
532 "In the worst case, this is an @math{O(N^2)} algorithm because\n"
533 "it must check each element against all those preceding it. For\n"
534 "long lists it is more efficient to sort and then compare only\n"
535 "adjacent elements.")
536 #define FUNC_NAME s_scm_srfi1_delete_duplicates
538 scm_t_trampoline_2 equal_p
;
539 SCM ret
, *p
, keeplst
, item
, l
;
542 /* ret is the new list constructed. p is where to append, initially &ret
543 then SCM_CDRLOC of the last pair. lst is advanced as each element is
546 Elements retained are not immediately appended to ret, instead keeplst
547 is the last pair in lst which is to be kept but is not yet copied.
548 Initially this is the first pair of lst, since the first element is
551 *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all
552 the elements retained, making the equality search loop easy.
554 If an item must be deleted, elements from keeplst (inclusive) to lst
555 (exclusive) must be copied and appended to ret. When there's no more
556 deletions, *p is left set to keeplst, so ret shares structure with the
557 original lst. (ret will be the entire original lst if there are no
560 /* skip to end if an empty list (or something invalid) */
563 if (SCM_UNBNDP (pred
))
564 equal_p
= equal_trampoline
;
567 SCM_VALIDATE_PROC (SCM_ARG2
, pred
);
568 equal_p
= scm_call_2
;
575 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
577 item
= SCM_CAR (lst
);
579 /* look for item in "ret" list */
580 for (l
= ret
; scm_is_pair (l
); l
= SCM_CDR (l
))
582 if (scm_is_true (equal_p (pred
, SCM_CAR (l
), item
)))
584 /* "item" is a duplicate, so copy keeplst onto ret */
586 p
= list_copy_part (keeplst
, count
, p
);
588 keeplst
= SCM_CDR (lst
); /* elem after the one deleted */
594 /* look for item in "keeplst" list
595 be careful traversing, in case nasty code changed the cdrs */
596 for (i
= 0, l
= keeplst
;
597 i
< count
&& scm_is_pair (l
);
598 i
++, l
= SCM_CDR (l
))
599 if (scm_is_true (equal_p (pred
, SCM_CAR (l
), item
)))
602 /* keep this element */
608 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG1
, FUNC_NAME
, "list");
610 /* share tail of keeplst items */
618 SCM_DEFINE (scm_srfi1_delete_duplicates_x
, "delete-duplicates!", 1, 1, 0,
620 "Return a list containing the elements of @var{lst} but without\n"
623 "When elements are equal, only the first in @var{lst} is\n"
624 "retained. Equal elements can be anywhere in @var{lst}, they\n"
625 "don't have to be adjacent. The returned list will have the\n"
626 "retained elements in the same order as they were in @var{lst}.\n"
628 "Equality is determined by @var{pred}, or @code{equal?} if not\n"
629 "given. Calls @code{(pred x y)} are made with element @var{x}\n"
630 "being before @var{y} in @var{lst}. A call is made at most once\n"
631 "for each combination, but the sequence of the calls across the\n"
632 "elements is unspecified.\n"
634 "@var{lst} may be modified to construct the returned list.\n"
636 "In the worst case, this is an @math{O(N^2)} algorithm because\n"
637 "it must check each element against all those preceding it. For\n"
638 "long lists it is more efficient to sort and then compare only\n"
639 "adjacent elements.")
640 #define FUNC_NAME s_scm_srfi1_delete_duplicates_x
642 scm_t_trampoline_2 equal_p
;
643 SCM ret
, endret
, item
, l
;
645 /* ret is the return list, constructed from the pairs in lst. endret is
646 the last pair of ret, initially the first pair. lst is advanced as
647 elements are considered. */
649 /* skip to end if an empty list (or something invalid) */
651 if (scm_is_pair (lst
))
653 if (SCM_UNBNDP (pred
))
654 equal_p
= equal_trampoline
;
657 SCM_VALIDATE_PROC (SCM_ARG2
, pred
);
658 equal_p
= scm_call_2
;
663 /* loop over lst elements starting from second */
667 if (! scm_is_pair (lst
))
669 item
= SCM_CAR (lst
);
671 /* is item equal to any element from ret to endret (inclusive)? */
675 if (scm_is_true (equal_p (pred
, SCM_CAR (l
), item
)))
676 break; /* equal, forget this element */
678 if (scm_is_eq (l
, endret
))
680 /* not equal to any, so append this pair */
681 SCM_SETCDR (endret
, lst
);
689 /* terminate, in case last element was deleted */
690 SCM_SETCDR (endret
, SCM_EOL
);
693 /* demand that lst was a proper list */
694 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG1
, FUNC_NAME
, "list");
701 SCM_DEFINE (scm_srfi1_drop_right
, "drop-right", 2, 0, 0,
703 "Return a new list containing all except the last @var{n}\n"
704 "elements of @var{lst}.")
705 #define FUNC_NAME s_scm_srfi1_drop_right
707 SCM tail
= scm_list_tail (lst
, n
);
710 while (scm_is_pair (tail
))
712 *rend
= scm_cons (SCM_CAR (lst
), SCM_EOL
);
713 rend
= SCM_CDRLOC (*rend
);
716 tail
= SCM_CDR (tail
);
718 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
724 SCM_DEFINE (scm_srfi1_drop_right_x
, "drop-right!", 2, 0, 0,
726 "Return the a list containing the @var{n} last elements of\n"
727 "@var{lst}. @var{lst} may be modified to build the return.")
728 #define FUNC_NAME s_scm_srfi1_drop_right_x
732 if (scm_is_eq (n
, SCM_INUM0
))
735 tail
= scm_list_tail (lst
, n
);
738 /* p and tail work along the list, p being the cdrloc of the cell n steps
740 for ( ; scm_is_pair (tail
); tail
= SCM_CDR (tail
))
743 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
751 SCM_DEFINE (scm_srfi1_drop_while
, "drop-while", 2, 0, 0,
753 "Drop the longest initial prefix of @var{lst} whose elements all\n"
754 "satisfy the predicate @var{pred}.")
755 #define FUNC_NAME s_scm_srfi1_drop_while
757 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
759 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
760 if (scm_is_false (scm_call_1 (pred
, SCM_CAR (lst
))))
763 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
770 SCM_DEFINE (scm_srfi1_eighth
, "eighth", 1, 0, 0,
772 "Return the eighth element of @var{lst}.")
773 #define FUNC_NAME s_scm_srfi1_eighth
775 return scm_list_ref (lst
, SCM_I_MAKINUM (7));
780 SCM_DEFINE (scm_srfi1_fifth
, "fifth", 1, 0, 0,
782 "Return the fifth element of @var{lst}.")
783 #define FUNC_NAME s_scm_srfi1_fifth
785 return scm_list_ref (lst
, SCM_I_MAKINUM (4));
790 SCM_DEFINE (scm_srfi1_filter_map
, "filter-map", 2, 0, 1,
791 (SCM proc
, SCM list1
, SCM rest
),
792 "Apply @var{proc} to to the elements of @var{list1} @dots{} and\n"
793 "return a list of the results as per SRFI-1 @code{map}, except\n"
794 "that any @code{#f} results are omitted from the list returned.")
795 #define FUNC_NAME s_scm_srfi1_filter_map
797 SCM ret
, *loc
, elem
, newcell
, lst
;
800 SCM_VALIDATE_REST_ARGUMENT (rest
);
805 if (scm_is_null (rest
))
808 SCM_VALIDATE_PROC (SCM_ARG1
, proc
);
810 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
812 elem
= scm_call_1 (proc
, SCM_CAR (list1
));
813 if (scm_is_true (elem
))
815 newcell
= scm_cons (elem
, SCM_EOL
);
817 loc
= SCM_CDRLOC (newcell
);
821 /* check below that list1 is a proper list, and done */
826 else if (scm_is_null (SCM_CDR (rest
)))
829 SCM list2
= SCM_CAR (rest
);
830 SCM_VALIDATE_PROC (SCM_ARG1
, proc
);
834 if (! scm_is_pair (list1
))
836 if (! scm_is_pair (list2
))
840 goto check_lst_and_done
;
842 elem
= scm_call_2 (proc
, SCM_CAR (list1
), SCM_CAR (list2
));
843 if (scm_is_true (elem
))
845 newcell
= scm_cons (elem
, SCM_EOL
);
847 loc
= SCM_CDRLOC (newcell
);
849 list1
= SCM_CDR (list1
);
850 list2
= SCM_CDR (list2
);
855 /* three or more lists */
859 /* vec is the list arguments */
860 vec
= scm_vector (scm_cons (list1
, rest
));
861 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
863 /* args is the argument list to pass to proc, same length as vec,
864 re-used for each call */
865 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
869 /* first elem of each list in vec into args, and step those
870 vec entries onto their next element */
871 for (i
= 0, a
= args
, argnum
= 2;
873 i
++, a
= SCM_CDR (a
), argnum
++)
875 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
876 if (! scm_is_pair (lst
))
877 goto check_lst_and_done
;
878 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for proc */
879 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
882 elem
= scm_apply (proc
, args
, SCM_EOL
);
883 if (scm_is_true (elem
))
885 newcell
= scm_cons (elem
, SCM_EOL
);
887 loc
= SCM_CDRLOC (newcell
);
893 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
899 SCM_DEFINE (scm_srfi1_find
, "find", 2, 0, 0,
901 "Return the first element of @var{lst} which satisfies the\n"
902 "predicate @var{pred}, or return @code{#f} if no such element is\n"
904 #define FUNC_NAME s_scm_srfi1_find
906 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
908 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
910 SCM elem
= SCM_CAR (lst
);
911 if (scm_is_true (scm_call_1 (pred
, elem
)))
914 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
921 SCM_DEFINE (scm_srfi1_find_tail
, "find-tail", 2, 0, 0,
923 "Return the first pair of @var{lst} whose @sc{car} satisfies the\n"
924 "predicate @var{pred}, or return @code{#f} if no such element is\n"
926 #define FUNC_NAME s_scm_srfi1_find_tail
928 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
930 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
931 if (scm_is_true (scm_call_1 (pred
, SCM_CAR (lst
))))
933 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
940 SCM_DEFINE (scm_srfi1_fold
, "fold", 3, 0, 1,
941 (SCM proc
, SCM init
, SCM list1
, SCM rest
),
942 "Apply @var{proc} to the elements of @var{lst1} @dots{}\n"
943 "@var{lstN} to build a result, and return that result.\n"
945 "Each @var{proc} call is @code{(@var{proc} @var{elem1} @dots{}\n"
946 "@var{elemN} @var{previous})}, where @var{elem1} is from\n"
947 "@var{lst1}, through @var{elemN} from @var{lstN}.\n"
948 "@var{previous} is the return from the previous call to\n"
949 "@var{proc}, or the given @var{init} for the first call. If any\n"
950 "list is empty, just @var{init} is returned.\n"
952 "@code{fold} works through the list elements from first to last.\n"
953 "The following shows a list reversal and the calls it makes,\n"
956 "(fold cons '() '(1 2 3))\n"
961 "@result{} (3 2 1)\n"
964 "If @var{lst1} through @var{lstN} have different lengths,\n"
965 "@code{fold} stops when the end of the shortest is reached.\n"
966 "Ie.@: elements past the length of the shortest are ignored in\n"
967 "the other @var{lst}s. At least one @var{lst} must be\n"
970 "The way @code{fold} builds a result from iterating is quite\n"
971 "general, it can do more than other iterations like say\n"
972 "@code{map} or @code{filter}. The following for example removes\n"
973 "adjacent duplicate elements from a list,\n"
976 "(define (delete-adjacent-duplicates lst)\n"
977 " (fold-right (lambda (elem ret)\n"
978 " (if (equal? elem (first ret))\n"
980 " (cons elem ret)))\n"
981 " (list (last lst))\n"
983 "(delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))\n"
984 "@result{} (1 2 3 4 5)\n"
987 "Clearly the same sort of thing can be done with a\n"
988 "@code{for-each} and a variable in which to build the result,\n"
989 "but a self-contained @var{proc} can be re-used in multiple\n"
990 "contexts, where a @code{for-each} would have to be written out\n"
992 #define FUNC_NAME s_scm_srfi1_fold
996 SCM_VALIDATE_REST_ARGUMENT (rest
);
998 if (scm_is_null (rest
))
1001 SCM_VALIDATE_PROC (SCM_ARG1
, proc
);
1003 for ( ; scm_is_pair (list1
); list1
= SCM_CDR (list1
))
1004 init
= scm_call_2 (proc
, SCM_CAR (list1
), init
);
1006 /* check below that list1 is a proper list, and done */
1012 /* two or more lists */
1016 /* vec is the list arguments */
1017 vec
= scm_vector (scm_cons (list1
, rest
));
1018 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
1020 /* args is the argument list to pass to proc, same length as vec,
1021 re-used for each call */
1022 args
= scm_make_list (SCM_I_MAKINUM (len
+1), SCM_UNDEFINED
);
1026 /* first elem of each list in vec into args, and step those
1027 vec entries onto their next element */
1028 for (i
= 0, a
= args
, argnum
= 2;
1030 i
++, a
= SCM_CDR (a
), argnum
++)
1032 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
1033 if (! scm_is_pair (lst
))
1034 goto check_lst_and_done
;
1035 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for proc */
1036 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
1038 SCM_SETCAR (a
, init
);
1040 init
= scm_apply (proc
, args
, SCM_EOL
);
1045 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
1051 SCM_DEFINE (scm_srfi1_last
, "last", 1, 0, 0,
1053 "Like @code{cons}, but with interchanged arguments. Useful\n"
1054 "mostly when passed to higher-order procedures.")
1055 #define FUNC_NAME s_scm_srfi1_last
1057 SCM pair
= scm_last_pair (lst
);
1058 /* scm_last_pair returns SCM_EOL for an empty list */
1059 SCM_VALIDATE_CONS (SCM_ARG1
, pair
);
1060 return SCM_CAR (pair
);
1065 SCM_DEFINE (scm_srfi1_length_plus
, "length+", 1, 0, 0,
1067 "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n"
1069 #define FUNC_NAME s_scm_srfi1_length_plus
1071 long len
= scm_ilength (lst
);
1072 return (len
>= 0 ? SCM_I_MAKINUM (len
) : SCM_BOOL_F
);
1077 SCM_DEFINE (scm_srfi1_list_index
, "list-index", 2, 0, 1,
1078 (SCM pred
, SCM list1
, SCM rest
),
1079 "Return the index of the first set of elements, one from each of\n"
1080 "@var{lst1}@dots{}@var{lstN}, which satisfies @var{pred}.\n"
1082 "@var{pred} is called as @code{(@var{pred} elem1 @dots{}\n"
1083 "elemN)}. Searching stops when the end of the shortest\n"
1084 "@var{lst} is reached. The return index starts from 0 for the\n"
1085 "first set of elements. If no set of elements pass then the\n"
1086 "return is @code{#f}.\n"
1089 "(list-index odd? '(2 4 6 9)) @result{} 3\n"
1090 "(list-index = '(1 2 3) '(3 1 2)) @result{} #f\n"
1092 #define FUNC_NAME s_scm_srfi1_list_index
1097 SCM_VALIDATE_REST_ARGUMENT (rest
);
1099 if (scm_is_null (rest
))
1102 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
1104 for ( ; scm_is_pair (list1
); n
++, list1
= SCM_CDR (list1
))
1105 if (scm_is_true (scm_call_1 (pred
, SCM_CAR (list1
))))
1106 return SCM_I_MAKINUM (n
);
1108 /* not found, check below that list1 is a proper list */
1113 else if (scm_is_pair (rest
) && scm_is_null (SCM_CDR (rest
)))
1116 SCM list2
= SCM_CAR (rest
);
1117 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
1121 if (! scm_is_pair (list1
))
1123 if (! scm_is_pair (list2
))
1129 if (scm_is_true (scm_call_2 (pred
,
1130 SCM_CAR (list1
), SCM_CAR (list2
))))
1131 return SCM_I_MAKINUM (n
);
1133 list1
= SCM_CDR (list1
);
1134 list2
= SCM_CDR (list2
);
1139 /* three or more lists */
1143 /* vec is the list arguments */
1144 vec
= scm_vector (scm_cons (list1
, rest
));
1145 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
1147 /* args is the argument list to pass to pred, same length as vec,
1148 re-used for each call */
1149 args
= scm_make_list (SCM_I_MAKINUM (len
), SCM_UNDEFINED
);
1153 /* first elem of each list in vec into args, and step those
1154 vec entries onto their next element */
1155 for (i
= 0, a
= args
, argnum
= 2;
1157 i
++, a
= SCM_CDR (a
), argnum
++)
1159 lst
= SCM_SIMPLE_VECTOR_REF (vec
, i
); /* list argument */
1160 if (! scm_is_pair (lst
))
1161 goto not_found_check_lst
;
1162 SCM_SETCAR (a
, SCM_CAR (lst
)); /* arg for pred */
1163 SCM_SIMPLE_VECTOR_SET (vec
, i
, SCM_CDR (lst
)); /* rest of lst */
1166 if (scm_is_true (scm_apply (pred
, args
, SCM_EOL
)))
1167 return SCM_I_MAKINUM (n
);
1171 not_found_check_lst
:
1172 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, argnum
, FUNC_NAME
, "list");
1178 /* This routine differs from the core list-copy in allowing improper lists.
1179 Maybe the core could allow them similarly. */
1181 SCM_DEFINE (scm_srfi1_list_copy
, "list-copy", 1, 0, 0,
1183 "Return a copy of the given list @var{lst}.\n"
1185 "@var{lst} can be a proper or improper list. And if @var{lst}\n"
1186 "is not a pair then it's treated as the final tail of an\n"
1187 "improper list and simply returned.")
1188 #define FUNC_NAME s_scm_srfi1_list_copy
1195 fill_here
= &newlst
;
1198 while (scm_is_pair (from_here
))
1201 c
= scm_cons (SCM_CAR (from_here
), SCM_CDR (from_here
));
1203 fill_here
= SCM_CDRLOC (c
);
1204 from_here
= SCM_CDR (from_here
);
1211 SCM_DEFINE (scm_srfi1_list_tabulate
, "list-tabulate", 2, 0, 0,
1213 "Return an @var{n}-element list, where each list element is\n"
1214 "produced by applying the procedure @var{init-proc} to the\n"
1215 "corresponding list index. The order in which @var{init-proc}\n"
1216 "is applied to the indices is not specified.")
1217 #define FUNC_NAME s_scm_srfi1_list_tabulate
1221 nn
= scm_to_signed_integer (n
, 0, LONG_MAX
);
1222 SCM_VALIDATE_PROC (SCM_ARG2
, proc
);
1223 for (i
= nn
-1; i
>= 0; i
--)
1224 ret
= scm_cons (scm_call_1 (proc
, scm_from_long (i
)), ret
);
1230 SCM_DEFINE (scm_srfi1_lset_adjoin
, "lset-adjoin", 2, 0, 1,
1231 (SCM equal
, SCM lst
, SCM rest
),
1232 "Add to @var{list} any of the given @var{elem}s not already in\n"
1233 "the list. @var{elem}s are @code{cons}ed onto the start of\n"
1234 "@var{list} (so the return shares a common tail with\n"
1235 "@var{list}), but the order they're added is unspecified.\n"
1237 "The given @var{=} procedure is used for comparing elements,\n"
1238 "called as @code{(@var{=} listelem elem)}, ie.@: the second\n"
1239 "argument is one of the given @var{elem} parameters.\n"
1242 "(lset-adjoin eqv? '(1 2 3) 4 1 5) @result{} (5 4 1 2 3)\n"
1244 #define FUNC_NAME s_scm_srfi1_lset_adjoin
1248 SCM_VALIDATE_PROC (SCM_ARG1
, equal
);
1249 SCM_VALIDATE_REST_ARGUMENT (rest
);
1251 /* It's not clear if duplicates among the `rest' elements are meant to be
1252 cast out. The spec says `=' is called as (= list-elem rest-elem),
1253 suggesting perhaps not, but the reference implementation shows the
1254 "list" at each stage as including those "rest" elements already added.
1255 The latter corresponds to what's described for lset-union, so that's
1256 what's done here. */
1258 for ( ; scm_is_pair (rest
); rest
= SCM_CDR (rest
))
1260 elem
= SCM_CAR (rest
);
1262 for (l
= lst
; scm_is_pair (l
); l
= SCM_CDR (l
))
1263 if (scm_is_true (scm_call_2 (equal
, SCM_CAR (l
), elem
)))
1264 goto next_elem
; /* elem already in lst, don't add */
1266 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(l
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1268 /* elem is not equal to anything already in lst, add it */
1269 lst
= scm_cons (elem
, lst
);
1280 SCM_DEFINE (scm_srfi1_lset_difference_x
, "lset-difference!", 2, 0, 1,
1281 (SCM equal
, SCM lst
, SCM rest
),
1282 "Return @var{lst} with any elements in the lists in @var{rest}\n"
1283 "removed (ie.@: subtracted). For only one @var{lst} argument,\n"
1284 "just that list is returned.\n"
1286 "The given @var{equal} procedure is used for comparing elements,\n"
1287 "called as @code{(@var{equal} elem1 elemN)}. The first argument\n"
1288 "is from @var{lst} and the second from one of the subsequent\n"
1289 "lists. But exactly which calls are made and in what order is\n"
1293 "(lset-difference! eqv? (list 'x 'y)) @result{} (x y)\n"
1294 "(lset-difference! eqv? (list 1 2 3) '(3 1)) @result{} (2)\n"
1295 "(lset-difference! eqv? (list 1 2 3) '(3) '(2)) @result{} (1)\n"
1298 "@code{lset-difference!} may modify @var{lst} to form its\n"
1300 #define FUNC_NAME s_scm_srfi1_lset_difference_x
1302 SCM ret
, *pos
, elem
, r
, b
;
1305 SCM_VALIDATE_PROC (SCM_ARG1
, equal
);
1306 SCM_VALIDATE_REST_ARGUMENT (rest
);
1310 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1312 elem
= SCM_CAR (lst
);
1314 for (r
= rest
, argnum
= SCM_ARG3
;
1316 r
= SCM_CDR (r
), argnum
++)
1318 for (b
= SCM_CAR (r
); scm_is_pair (b
); b
= SCM_CDR (b
))
1319 if (scm_is_true (scm_call_2 (equal
, elem
, SCM_CAR (b
))))
1320 goto next_elem
; /* equal to elem, so drop that elem */
1322 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (b
), b
, argnum
, FUNC_NAME
,"list");
1325 /* elem not equal to anything in later lists, so keep it */
1327 pos
= SCM_CDRLOC (lst
);
1332 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1340 /* Typechecking for multi-argument MAP and FOR-EACH.
1342 Verify that each element of the vector ARGV, except for the first,
1343 is a list and return minimum length. Attribute errors to WHO,
1344 and claim that the i'th element of ARGV is WHO's i+2'th argument. */
1346 check_map_args (SCM argv
,
1356 for (i
= SCM_SIMPLE_VECTOR_LENGTH (argv
) - 1; i
>= 1; i
--)
1359 elt
= SCM_SIMPLE_VECTOR_REF (argv
, i
);
1361 if (!(scm_is_null (elt
) || scm_is_pair (elt
)))
1362 goto check_map_error
;
1364 elt_len
= srfi1_ilength (elt
);
1366 goto check_map_error
;
1368 if (len
< 0 || (elt_len
>= 0 && elt_len
< len
))
1378 scm_apply_generic (gf
, scm_cons (proc
, args
));
1380 scm_wrong_type_arg (who
, i
+ 2, elt
);
1383 scm_remember_upto_here_1 (argv
);
1388 SCM_GPROC (s_srfi1_map
, "map", 2, 0, 1, scm_srfi1_map
, g_srfi1_map
);
1390 /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s)
1391 sequentially, starting with the first element(s). This is used in
1392 the Scheme procedure `map-in-order', which guarantees sequential
1393 behaviour, is implemented using scm_map. If the behaviour changes,
1394 we need to update `map-in-order'.
1398 scm_srfi1_map (SCM proc
, SCM arg1
, SCM args
)
1399 #define FUNC_NAME s_srfi1_map
1405 len
= srfi1_ilength (arg1
);
1406 SCM_GASSERTn ((scm_is_null (arg1
) || scm_is_pair (arg1
)) && len
>= -1,
1408 scm_cons2 (proc
, arg1
, args
), SCM_ARG2
, s_srfi1_map
);
1409 SCM_VALIDATE_REST_ARGUMENT (args
);
1410 if (scm_is_null (args
))
1412 SCM_GASSERT2 (scm_is_true (scm_procedure_p (proc
)), g_srfi1_map
,
1413 proc
, arg1
, SCM_ARG1
, s_srfi1_map
);
1414 SCM_GASSERT2 (len
>= 0, g_srfi1_map
, proc
, arg1
, SCM_ARG2
, s_srfi1_map
);
1415 while (SCM_NIMP (arg1
))
1417 *pres
= scm_list_1 (scm_call_1 (proc
, SCM_CAR (arg1
)));
1418 pres
= SCM_CDRLOC (*pres
);
1419 arg1
= SCM_CDR (arg1
);
1423 if (scm_is_null (SCM_CDR (args
)))
1425 SCM arg2
= SCM_CAR (args
);
1426 int len2
= srfi1_ilength (arg2
);
1427 SCM_GASSERTn (scm_is_true (scm_procedure_p (proc
)), g_srfi1_map
,
1428 scm_cons2 (proc
, arg1
, args
), SCM_ARG1
, s_srfi1_map
);
1429 if (len
< 0 || (len2
>= 0 && len2
< len
))
1431 SCM_GASSERTn ((scm_is_null (arg2
) || scm_is_pair (arg2
))
1432 && len
>= 0 && len2
>= -1,
1434 scm_cons2 (proc
, arg1
, args
),
1435 len2
>= 0 ? SCM_ARG2
: SCM_ARG3
,
1439 *pres
= scm_list_1 (scm_call_2 (proc
, SCM_CAR (arg1
), SCM_CAR (arg2
)));
1440 pres
= SCM_CDRLOC (*pres
);
1441 arg1
= SCM_CDR (arg1
);
1442 arg2
= SCM_CDR (arg2
);
1447 args
= scm_vector (arg1
= scm_cons (arg1
, args
));
1448 len
= check_map_args (args
, len
, g_srfi1_map
, proc
, arg1
, s_srfi1_map
);
1452 for (i
= SCM_SIMPLE_VECTOR_LENGTH (args
) - 1; i
>= 0; i
--)
1454 SCM elt
= SCM_SIMPLE_VECTOR_REF (args
, i
);
1455 arg1
= scm_cons (SCM_CAR (elt
), arg1
);
1456 SCM_SIMPLE_VECTOR_SET (args
, i
, SCM_CDR (elt
));
1458 *pres
= scm_list_1 (scm_apply (proc
, arg1
, SCM_EOL
));
1459 pres
= SCM_CDRLOC (*pres
);
1466 SCM_REGISTER_PROC (s_srfi1_map_in_order
, "map-in-order", 2, 0, 1, scm_srfi1_map
);
1468 SCM_GPROC (s_srfi1_for_each
, "for-each", 2, 0, 1, scm_srfi1_for_each
, g_srfi1_for_each
);
1471 scm_srfi1_for_each (SCM proc
, SCM arg1
, SCM args
)
1472 #define FUNC_NAME s_srfi1_for_each
1475 len
= srfi1_ilength (arg1
);
1476 SCM_GASSERTn ((scm_is_null (arg1
) || scm_is_pair (arg1
)) && len
>= -1,
1477 g_srfi1_for_each
, scm_cons2 (proc
, arg1
, args
),
1478 SCM_ARG2
, s_srfi1_for_each
);
1479 SCM_VALIDATE_REST_ARGUMENT (args
);
1480 if (scm_is_null (args
))
1482 SCM_GASSERT2 (scm_is_true (scm_procedure_p (proc
)), g_srfi1_for_each
,
1483 proc
, arg1
, SCM_ARG1
, s_srfi1_for_each
);
1484 SCM_GASSERT2 (len
>= 0, g_srfi1_for_each
, proc
, arg1
,
1485 SCM_ARG2
, s_srfi1_map
);
1486 while (SCM_NIMP (arg1
))
1488 scm_call_1 (proc
, SCM_CAR (arg1
));
1489 arg1
= SCM_CDR (arg1
);
1491 return SCM_UNSPECIFIED
;
1493 if (scm_is_null (SCM_CDR (args
)))
1495 SCM arg2
= SCM_CAR (args
);
1496 int len2
= srfi1_ilength (arg2
);
1497 SCM_GASSERTn (scm_is_true (scm_procedure_p (proc
)), g_srfi1_for_each
,
1498 scm_cons2 (proc
, arg1
, args
), SCM_ARG1
, s_srfi1_for_each
);
1499 if (len
< 0 || (len2
>= 0 && len2
< len
))
1501 SCM_GASSERTn ((scm_is_null (arg2
) || scm_is_pair (arg2
))
1502 && len
>= 0 && len2
>= -1,
1504 scm_cons2 (proc
, arg1
, args
),
1505 len2
>= 0 ? SCM_ARG2
: SCM_ARG3
,
1509 scm_call_2 (proc
, SCM_CAR (arg1
), SCM_CAR (arg2
));
1510 arg1
= SCM_CDR (arg1
);
1511 arg2
= SCM_CDR (arg2
);
1514 return SCM_UNSPECIFIED
;
1516 args
= scm_vector (arg1
= scm_cons (arg1
, args
));
1517 len
= check_map_args (args
, len
, g_srfi1_for_each
, proc
, arg1
,
1522 for (i
= SCM_SIMPLE_VECTOR_LENGTH (args
) - 1; i
>= 0; i
--)
1524 SCM elt
= SCM_SIMPLE_VECTOR_REF (args
, i
);
1525 arg1
= scm_cons (SCM_CAR (elt
), arg1
);
1526 SCM_SIMPLE_VECTOR_SET (args
, i
, SCM_CDR (elt
));
1528 scm_apply (proc
, arg1
, SCM_EOL
);
1531 return SCM_UNSPECIFIED
;
1536 SCM_DEFINE (scm_srfi1_member
, "member", 2, 1, 0,
1537 (SCM x
, SCM lst
, SCM pred
),
1538 "Return the first sublist of @var{lst} whose @sc{car} is equal\n"
1539 "to @var{x}. If @var{x} does not appear in @var{lst}, return\n"
1542 "Equality is determined by @code{equal?}, or by the equality\n"
1543 "predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n"
1544 "elem)}, ie.@: with the given @var{x} first, so for example to\n"
1545 "find the first element greater than 5,\n"
1548 "(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n"
1551 "This version of @code{member} extends the core @code{member} by\n"
1552 "accepting an equality predicate.")
1553 #define FUNC_NAME s_scm_srfi1_member
1555 scm_t_trampoline_2 equal_p
;
1556 SCM_VALIDATE_LIST (2, lst
);
1557 if (SCM_UNBNDP (pred
))
1558 equal_p
= equal_trampoline
;
1561 SCM_VALIDATE_PROC (SCM_ARG3
, pred
);
1562 equal_p
= scm_call_2
;
1564 for (; !SCM_NULL_OR_NIL_P (lst
); lst
= SCM_CDR (lst
))
1566 if (scm_is_true (equal_p (pred
, x
, SCM_CAR (lst
))))
1573 SCM_DEFINE (scm_srfi1_assoc
, "assoc", 2, 1, 0,
1574 (SCM key
, SCM alist
, SCM pred
),
1575 "Behaves like @code{assq} but uses third argument @var{pred?}\n"
1576 "for key comparison. If @var{pred?} is not supplied,\n"
1577 "@code{equal?} is used. (Extended from R5RS.)\n")
1578 #define FUNC_NAME s_scm_srfi1_assoc
1581 scm_t_trampoline_2 equal_p
;
1582 if (SCM_UNBNDP (pred
))
1583 equal_p
= equal_trampoline
;
1586 SCM_VALIDATE_PROC (SCM_ARG3
, pred
);
1587 equal_p
= scm_call_2
;
1589 for(; scm_is_pair (ls
); ls
= SCM_CDR (ls
))
1591 SCM tmp
= SCM_CAR (ls
);
1592 SCM_ASSERT_TYPE (scm_is_pair (tmp
), alist
, SCM_ARG2
, FUNC_NAME
,
1593 "association list");
1594 if (scm_is_true (equal_p (pred
, key
, SCM_CAR (tmp
))))
1597 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls
), alist
, SCM_ARG2
, FUNC_NAME
,
1598 "association list");
1604 SCM_DEFINE (scm_srfi1_ninth
, "ninth", 1, 0, 0,
1606 "Return the ninth element of @var{lst}.")
1607 #define FUNC_NAME s_scm_srfi1_ninth
1609 return scm_list_ref (lst
, scm_from_int (8));
1614 SCM_DEFINE (scm_srfi1_not_pair_p
, "not-pair?", 1, 0, 0,
1616 "Return @code{#t} is @var{obj} is not a pair, @code{#f}\n"
1619 "This is shorthand notation @code{(not (pair? @var{obj}))} and\n"
1620 "is supposed to be used for end-of-list checking in contexts\n"
1621 "where dotted lists are allowed.")
1622 #define FUNC_NAME s_scm_srfi1_not_pair_p
1624 return scm_from_bool (! scm_is_pair (obj
));
1629 SCM_DEFINE (scm_srfi1_partition
, "partition", 2, 0, 0,
1630 (SCM pred
, SCM list
),
1631 "Partition the elements of @var{list} with predicate @var{pred}.\n"
1632 "Return two values: the list of elements satifying @var{pred} and\n"
1633 "the list of elements @emph{not} satisfying @var{pred}. The order\n"
1634 "of the output lists follows the order of @var{list}. @var{list}\n"
1635 "is not mutated. One of the output lists may share memory with @var{list}.\n")
1636 #define FUNC_NAME s_scm_srfi1_partition
1638 /* In this implementation, the output lists don't share memory with
1639 list, because it's probably not worth the effort. */
1640 SCM orig_list
= list
;
1641 SCM kept
= scm_cons(SCM_EOL
, SCM_EOL
);
1642 SCM kept_tail
= kept
;
1643 SCM dropped
= scm_cons(SCM_EOL
, SCM_EOL
);
1644 SCM dropped_tail
= dropped
;
1646 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
1648 for (; !SCM_NULL_OR_NIL_P (list
); list
= SCM_CDR(list
)) {
1651 /* Make sure LIST is not a dotted list. */
1652 SCM_ASSERT (scm_is_pair (list
), orig_list
, SCM_ARG2
, FUNC_NAME
);
1654 elt
= SCM_CAR (list
);
1655 new_tail
= scm_cons (SCM_CAR (list
), SCM_EOL
);
1657 if (scm_is_true (scm_call_1 (pred
, elt
))) {
1658 SCM_SETCDR(kept_tail
, new_tail
);
1659 kept_tail
= new_tail
;
1662 SCM_SETCDR(dropped_tail
, new_tail
);
1663 dropped_tail
= new_tail
;
1666 /* re-use the initial conses for the values list */
1667 SCM_SETCAR(kept
, SCM_CDR(kept
));
1668 SCM_SETCDR(kept
, dropped
);
1669 SCM_SETCAR(dropped
, SCM_CDR(dropped
));
1670 SCM_SETCDR(dropped
, SCM_EOL
);
1671 return scm_values(kept
);
1676 SCM_DEFINE (scm_srfi1_partition_x
, "partition!", 2, 0, 0,
1677 (SCM pred
, SCM lst
),
1678 "Split @var{lst} into those elements which do and don't satisfy\n"
1679 "the predicate @var{pred}.\n"
1681 "The return is two values (@pxref{Multiple Values}), the first\n"
1682 "being a list of all elements from @var{lst} which satisfy\n"
1683 "@var{pred}, the second a list of those which do not.\n"
1685 "The elements in the result lists are in the same order as in\n"
1686 "@var{lst} but the order in which the calls @code{(@var{pred}\n"
1687 "elem)} are made on the list elements is unspecified.\n"
1689 "@var{lst} may be modified to construct the return lists.")
1690 #define FUNC_NAME s_scm_srfi1_partition_x
1692 SCM tlst
, flst
, *tp
, *fp
;
1694 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
1696 /* tlst and flst are the lists of true and false elements. tp and fp are
1697 where to store to append to them, initially &tlst and &flst, then
1698 SCM_CDRLOC of the last pair in the respective lists. */
1705 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1707 if (scm_is_true (scm_call_1 (pred
, SCM_CAR (lst
))))
1710 tp
= SCM_CDRLOC (lst
);
1715 fp
= SCM_CDRLOC (lst
);
1719 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1721 /* terminate whichever didn't get the last element(s) */
1725 return scm_values (scm_list_2 (tlst
, flst
));
1730 SCM_DEFINE (scm_srfi1_reduce
, "reduce", 3, 0, 0,
1731 (SCM proc
, SCM def
, SCM lst
),
1732 "@code{reduce} is a variant of @code{fold}, where the first call\n"
1733 "to @var{proc} is on two elements from @var{lst}, rather than\n"
1734 "one element and a given initial value.\n"
1736 "If @var{lst} is empty, @code{reduce} returns @var{def} (this is\n"
1737 "the only use for @var{def}). If @var{lst} has just one element\n"
1738 "then that's the return value. Otherwise @var{proc} is called\n"
1739 "on the elements of @var{lst}.\n"
1741 "Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1742 "@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1743 "second and subsequent elements of @var{lst}), and\n"
1744 "@var{previous} is the return from the previous call to\n"
1745 "@var{proc}. The first element of @var{lst} is the\n"
1746 "@var{previous} for the first call to @var{proc}.\n"
1748 "For example, the following adds a list of numbers, the calls\n"
1749 "made to @code{+} are shown. (Of course @code{+} accepts\n"
1750 "multiple arguments and can add a list directly, with\n"
1754 "(reduce + 0 '(5 6 7)) @result{} 18\n"
1756 "(+ 6 5) @result{} 11\n"
1757 "(+ 7 11) @result{} 18\n"
1760 "@code{reduce} can be used instead of @code{fold} where the\n"
1761 "@var{init} value is an ``identity'', meaning a value which\n"
1762 "under @var{proc} doesn't change the result, in this case 0 is\n"
1763 "an identity since @code{(+ 5 0)} is just 5. @code{reduce}\n"
1764 "avoids that unnecessary call.")
1765 #define FUNC_NAME s_scm_srfi1_reduce
1768 SCM_VALIDATE_PROC (SCM_ARG1
, proc
);
1769 ret
= def
; /* if lst is empty */
1770 if (scm_is_pair (lst
))
1772 ret
= SCM_CAR (lst
); /* if lst has one element */
1774 for (lst
= SCM_CDR (lst
); scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1775 ret
= scm_call_2 (proc
, SCM_CAR (lst
), ret
);
1778 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG3
, FUNC_NAME
, "list");
1784 SCM_DEFINE (scm_srfi1_reduce_right
, "reduce-right", 3, 0, 0,
1785 (SCM proc
, SCM def
, SCM lst
),
1786 "@code{reduce-right} is a variant of @code{fold-right}, where\n"
1787 "the first call to @var{proc} is on two elements from @var{lst},\n"
1788 "rather than one element and a given initial value.\n"
1790 "If @var{lst} is empty, @code{reduce-right} returns @var{def}\n"
1791 "(this is the only use for @var{def}). If @var{lst} has just\n"
1792 "one element then that's the return value. Otherwise @var{proc}\n"
1793 "is called on the elements of @var{lst}.\n"
1795 "Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1796 "@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1797 "second last and then working back to the first element of\n"
1798 "@var{lst}), and @var{previous} is the return from the previous\n"
1799 "call to @var{proc}. The last element of @var{lst} is the\n"
1800 "@var{previous} for the first call to @var{proc}.\n"
1802 "For example, the following adds a list of numbers, the calls\n"
1803 "made to @code{+} are shown. (Of course @code{+} accepts\n"
1804 "multiple arguments and can add a list directly, with\n"
1808 "(reduce-right + 0 '(5 6 7)) @result{} 18\n"
1810 "(+ 6 7) @result{} 13\n"
1811 "(+ 5 13) @result{} 18\n"
1814 "@code{reduce-right} can be used instead of @code{fold-right}\n"
1815 "where the @var{init} value is an ``identity'', meaning a value\n"
1816 "which under @var{proc} doesn't change the result, in this case\n"
1817 "0 is an identity since @code{(+ 7 0)} is just 5.\n"
1818 "@code{reduce-right} avoids that unnecessary call.\n"
1820 "@code{reduce} should be preferred over @code{reduce-right} if\n"
1821 "the order of processing doesn't matter, or can be arranged\n"
1822 "either way, since @code{reduce} is a little more efficient.")
1823 #define FUNC_NAME s_scm_srfi1_reduce_right
1825 /* To work backwards across a list requires either repeatedly traversing
1826 to get each previous element, or using some memory for a reversed or
1827 random-access form. Repeated traversal might not be too terrible, but
1828 is of course quadratic complexity and hence to be avoided in case LST
1829 is long. A vector is preferred over a reversed list since it's more
1830 compact and is less work for the gc to collect. */
1834 SCM_VALIDATE_PROC (SCM_ARG1
, proc
);
1835 if (SCM_NULL_OR_NIL_P (lst
))
1838 vec
= scm_vector (lst
);
1839 len
= SCM_SIMPLE_VECTOR_LENGTH (vec
);
1841 ret
= SCM_SIMPLE_VECTOR_REF (vec
, len
-1);
1842 for (i
= len
-2; i
>= 0; i
--)
1843 ret
= scm_call_2 (proc
, SCM_SIMPLE_VECTOR_REF (vec
, i
), ret
);
1850 SCM_DEFINE (scm_srfi1_remove
, "remove", 2, 0, 0,
1851 (SCM pred
, SCM list
),
1852 "Return a list containing all elements from @var{lst} which do\n"
1853 "not satisfy the predicate @var{pred}. The elements in the\n"
1854 "result list have the same order as in @var{lst}. The order in\n"
1855 "which @var{pred} is applied to the list elements is not\n"
1857 #define FUNC_NAME s_scm_srfi1_remove
1862 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
1863 SCM_VALIDATE_LIST (2, list
);
1865 for (prev
= &res
, walk
= list
;
1867 walk
= SCM_CDR (walk
))
1869 if (scm_is_false (scm_call_1 (pred
, SCM_CAR (walk
))))
1871 *prev
= scm_cons (SCM_CAR (walk
), SCM_EOL
);
1872 prev
= SCM_CDRLOC (*prev
);
1881 SCM_DEFINE (scm_srfi1_remove_x
, "remove!", 2, 0, 0,
1882 (SCM pred
, SCM list
),
1883 "Return a list containing all elements from @var{list} which do\n"
1884 "not satisfy the predicate @var{pred}. The elements in the\n"
1885 "result list have the same order as in @var{list}. The order in\n"
1886 "which @var{pred} is applied to the list elements is not\n"
1887 "specified. @var{list} may be modified to build the return\n"
1889 #define FUNC_NAME s_scm_srfi1_remove_x
1893 SCM_VALIDATE_PROC (SCM_ARG1
, pred
);
1894 SCM_VALIDATE_LIST (2, list
);
1896 for (prev
= &list
, walk
= list
;
1898 walk
= SCM_CDR (walk
))
1900 if (scm_is_false (scm_call_1 (pred
, SCM_CAR (walk
))))
1901 prev
= SCM_CDRLOC (walk
);
1903 *prev
= SCM_CDR (walk
);
1911 SCM_DEFINE (scm_srfi1_seventh
, "seventh", 1, 0, 0,
1913 "Return the seventh element of @var{lst}.")
1914 #define FUNC_NAME s_scm_srfi1_seventh
1916 return scm_list_ref (lst
, scm_from_int (6));
1921 SCM_DEFINE (scm_srfi1_sixth
, "sixth", 1, 0, 0,
1923 "Return the sixth element of @var{lst}.")
1924 #define FUNC_NAME s_scm_srfi1_sixth
1926 return scm_list_ref (lst
, scm_from_int (5));
1931 SCM_DEFINE (scm_srfi1_span
, "span", 2, 0, 0,
1932 (SCM pred
, SCM lst
),
1933 "Return two values, the longest initial prefix of @var{lst}\n"
1934 "whose elements all satisfy the predicate @var{pred}, and the\n"
1935 "remainder of @var{lst}.")
1936 #define FUNC_NAME s_scm_srfi1_span
1940 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
1944 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
1946 SCM elem
= SCM_CAR (lst
);
1947 if (scm_is_false (scm_call_1 (pred
, elem
)))
1950 /* want this elem, tack it onto the end of ret */
1951 *p
= scm_cons (elem
, SCM_EOL
);
1952 p
= SCM_CDRLOC (*p
);
1954 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1957 return scm_values (scm_list_2 (ret
, lst
));
1962 SCM_DEFINE (scm_srfi1_span_x
, "span!", 2, 0, 0,
1963 (SCM pred
, SCM lst
),
1964 "Return two values, the longest initial prefix of @var{lst}\n"
1965 "whose elements all satisfy the predicate @var{pred}, and the\n"
1966 "remainder of @var{lst}. @var{lst} may be modified to form the\n"
1968 #define FUNC_NAME s_scm_srfi1_span_x
1972 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
1975 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
1977 if (scm_is_false (scm_call_1 (pred
, SCM_CAR (upto
))))
1980 /* want this element */
1981 p
= SCM_CDRLOC (upto
);
1983 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
1987 return scm_values (scm_list_2 (lst
, upto
));
1992 SCM_DEFINE (scm_srfi1_split_at
, "split-at", 2, 0, 0,
1994 "Return two values (multiple values), being a list of the\n"
1995 "elements before index @var{n} in @var{lst}, and a list of those\n"
1997 #define FUNC_NAME s_scm_srfi1_split_at
2000 /* pre is a list of elements before the i split point, loc is the CDRLOC
2001 of the last cell, ie. where to store to append to it */
2005 for (nn
= scm_to_size_t (n
); nn
!= 0; nn
--)
2007 SCM_VALIDATE_CONS (SCM_ARG1
, lst
);
2009 *loc
= scm_cons (SCM_CAR (lst
), SCM_EOL
);
2010 loc
= SCM_CDRLOC (*loc
);
2013 return scm_values (scm_list_2 (pre
, lst
));
2018 SCM_DEFINE (scm_srfi1_split_at_x
, "split-at!", 2, 0, 0,
2020 "Return two values (multiple values), being a list of the\n"
2021 "elements before index @var{n} in @var{lst}, and a list of those\n"
2022 "after. @var{lst} is modified to form those values.")
2023 #define FUNC_NAME s_scm_srfi1_split_at
2029 for (nn
= scm_to_size_t (n
); nn
!= 0; nn
--)
2031 SCM_VALIDATE_CONS (SCM_ARG1
, upto
);
2033 loc
= SCM_CDRLOC (upto
);
2034 upto
= SCM_CDR (upto
);
2038 return scm_values (scm_list_2 (lst
, upto
));
2043 SCM_DEFINE (scm_srfi1_take_x
, "take!", 2, 0, 0,
2045 "Return a list containing the first @var{n} elements of\n"
2047 #define FUNC_NAME s_scm_srfi1_take_x
2052 nn
= scm_to_signed_integer (n
, 0, LONG_MAX
);
2056 pos
= scm_list_tail (lst
, scm_from_long (nn
- 1));
2058 /* Must have at least one cell left, mustn't have reached the end of an
2059 n-1 element list. SCM_VALIDATE_CONS here gives the same error as
2060 scm_list_tail does on say an n-2 element list, though perhaps a range
2061 error would make more sense (for both). */
2062 SCM_VALIDATE_CONS (SCM_ARG1
, pos
);
2064 SCM_SETCDR (pos
, SCM_EOL
);
2070 SCM_DEFINE (scm_srfi1_take_right
, "take-right", 2, 0, 0,
2072 "Return the a list containing the @var{n} last elements of\n"
2074 #define FUNC_NAME s_scm_srfi1_take_right
2076 SCM tail
= scm_list_tail (lst
, n
);
2077 while (scm_is_pair (tail
))
2079 lst
= SCM_CDR (lst
);
2080 tail
= SCM_CDR (tail
);
2082 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail
), tail
, SCM_ARG1
, FUNC_NAME
, "list");
2088 SCM_DEFINE (scm_srfi1_take_while
, "take-while", 2, 0, 0,
2089 (SCM pred
, SCM lst
),
2090 "Return a new list which is the longest initial prefix of\n"
2091 "@var{lst} whose elements all satisfy the predicate @var{pred}.")
2092 #define FUNC_NAME s_scm_srfi1_take_while
2096 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
2100 for ( ; scm_is_pair (lst
); lst
= SCM_CDR (lst
))
2102 SCM elem
= SCM_CAR (lst
);
2103 if (scm_is_false (scm_call_1 (pred
, elem
)))
2106 /* want this elem, tack it onto the end of ret */
2107 *p
= scm_cons (elem
, SCM_EOL
);
2108 p
= SCM_CDRLOC (*p
);
2110 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
2118 SCM_DEFINE (scm_srfi1_take_while_x
, "take-while!", 2, 0, 0,
2119 (SCM pred
, SCM lst
),
2120 "Return the longest initial prefix of @var{lst} whose elements\n"
2121 "all satisfy the predicate @var{pred}. @var{lst} may be\n"
2122 "modified to form the return.")
2123 #define FUNC_NAME s_scm_srfi1_take_while_x
2127 SCM_ASSERT (scm_is_true (scm_procedure_p (pred
)), pred
, SCM_ARG1
, FUNC_NAME
);
2130 for (upto
= lst
; scm_is_pair (upto
); upto
= SCM_CDR (upto
))
2132 if (scm_is_false (scm_call_1 (pred
, SCM_CAR (upto
))))
2135 /* want this element */
2136 p
= SCM_CDRLOC (upto
);
2138 SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto
), lst
, SCM_ARG2
, FUNC_NAME
, "list");
2147 SCM_DEFINE (scm_srfi1_tenth
, "tenth", 1, 0, 0,
2149 "Return the tenth element of @var{lst}.")
2150 #define FUNC_NAME s_scm_srfi1_tenth
2152 return scm_list_ref (lst
, scm_from_int (9));
2157 SCM_DEFINE (scm_srfi1_xcons
, "xcons", 2, 0, 0,
2159 "Like @code{cons}, but with interchanged arguments. Useful\n"
2160 "mostly when passed to higher-order procedures.")
2161 #define FUNC_NAME s_scm_srfi1_xcons
2163 return scm_cons (a
, d
);
2169 scm_init_srfi_1 (void)
2171 SCM the_root_module
= scm_lookup_closure_module (SCM_BOOL_F
);
2172 #ifndef SCM_MAGIC_SNARFER
2173 #include "srfi/srfi-1.x"
2175 scm_c_extend_primitive_generic
2176 (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module
, "map")),
2177 SCM_VARIABLE_REF (scm_c_lookup ("map")));
2178 scm_c_extend_primitive_generic
2179 (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module
, "for-each")),
2180 SCM_VARIABLE_REF (scm_c_lookup ("for-each")));
2183 /* End of srfi-1.c. */