1
/* srfi-1.c --- SRFI-1 procedures for Guile
3
* Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006
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
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);
65
/* list_copy_part() copies the first COUNT cells of LST, puts the result at
66
*dst, and returns the SCM_CDRLOC of the last cell in that new list.
68
This function is designed to be careful about LST possibly having changed
69
in between the caller deciding what to copy, and the copy actually being
70
done here. The COUNT ensures we terminate if LST has become circular,
71
SCM_VALIDATE_CONS guards against a cdr in the list changed to some
76
list_copy_part (SCM lst, int count, SCM *dst)
77
#define FUNC_NAME "list_copy_part"
80
for ( ; count > 0; count--)
82
SCM_VALIDATE_CONS (SCM_ARGn, lst);
83
c = scm_cons (SCM_CAR (lst), SCM_EOL);
93
SCM_DEFINE (scm_srfi1_alist_copy, "alist-copy", 1, 0, 0,
95
"Return a copy of @var{alist}, copying both the pairs comprising\n"
96
"the list and those making the associations.")
97
#define FUNC_NAME s_scm_srfi1_alist_copy
101
/* ret is the list to return. p is where to append to it, initially &ret
102
then SCM_CDRLOC of the last pair. */
106
for ( ; scm_is_pair (alist); alist = SCM_CDR (alist))
108
elem = SCM_CAR (alist);
110
/* each element of alist must be a pair */
111
SCM_ASSERT_TYPE (scm_is_pair (elem), alist, SCM_ARG1, FUNC_NAME,
114
c = scm_cons (scm_cons (SCM_CAR (elem), SCM_CDR (elem)), SCM_EOL);
119
/* alist must be a proper list */
120
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (alist), alist, SCM_ARG1, FUNC_NAME,
128
SCM_DEFINE (scm_srfi1_append_reverse, "append-reverse", 2, 0, 0,
129
(SCM revhead, SCM tail),
130
"Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
131
"result. This is equivalent to @code{(append (reverse\n"
132
"@var{rev-head}) @var{tail})}, but its implementation is more\n"
136
"(append-reverse '(1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
138
#define FUNC_NAME s_scm_srfi1_append_reverse
140
while (scm_is_pair (revhead))
142
/* copy first element of revhead onto front of tail */
143
tail = scm_cons (SCM_CAR (revhead), tail);
144
revhead = SCM_CDR (revhead);
146
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME,
153
SCM_DEFINE (scm_srfi1_append_reverse_x, "append-reverse!", 2, 0, 0,
154
(SCM revhead, SCM tail),
155
"Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
156
"result. This is equivalent to @code{(append! (reverse!\n"
157
"@var{rev-head}) @var{tail})}, but its implementation is more\n"
161
"(append-reverse! (list 1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
164
"@var{rev-head} may be modified in order to produce the result.")
165
#define FUNC_NAME s_scm_srfi1_append_reverse_x
169
while (scm_is_pair (revhead))
171
/* take the first cons cell from revhead */
173
revhead = SCM_CDR (revhead);
175
/* make it the new start of tail, appending the previous */
176
SCM_SETCDR (newtail, tail);
179
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME,
186
SCM_DEFINE (scm_srfi1_break, "break", 2, 0, 0,
188
"Return two values, the longest initial prefix of @var{lst}\n"
189
"whose elements all fail the predicate @var{pred}, and the\n"
190
"remainder of @var{lst}.\n"
192
"Note that the name @code{break} conflicts with the @code{break}\n"
193
"binding established by @code{while}. Applications wanting to\n"
194
"use @code{break} from within a @code{while} loop will need to\n"
195
"make a new define under a different name.")
196
#define FUNC_NAME s_scm_srfi1_break
198
scm_t_trampoline_1 pred_tramp;
201
pred_tramp = scm_trampoline_1 (pred);
202
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
206
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
208
SCM elem = SCM_CAR (lst);
209
if (scm_is_true (pred_tramp (pred, elem)))
212
/* want this elem, tack it onto the end of ret */
213
*p = scm_cons (elem, SCM_EOL);
216
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
219
return scm_values (scm_list_2 (ret, lst));
224
SCM_DEFINE (scm_srfi1_break_x, "break!", 2, 0, 0,
226
"Return two values, the longest initial prefix of @var{lst}\n"
227
"whose elements all fail the predicate @var{pred}, and the\n"
228
"remainder of @var{lst}. @var{lst} may be modified to form the\n"
230
#define FUNC_NAME s_scm_srfi1_break_x
233
scm_t_trampoline_1 pred_tramp;
235
pred_tramp = scm_trampoline_1 (pred);
236
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
239
for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto))
241
if (scm_is_true (pred_tramp (pred, SCM_CAR (upto))))
244
/* want this element */
245
p = SCM_CDRLOC (upto);
247
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list");
251
return scm_values (scm_list_2 (lst, upto));
256
SCM_DEFINE (scm_srfi1_car_plus_cdr, "car+cdr", 1, 0, 0,
258
"Return two values, the @sc{car} and the @sc{cdr} of @var{pair}.")
259
#define FUNC_NAME s_scm_srfi1_car_plus_cdr
261
SCM_VALIDATE_CONS (SCM_ARG1, pair);
262
return scm_values (scm_list_2 (SCM_CAR (pair), SCM_CDR (pair)));
267
SCM_DEFINE (scm_srfi1_concatenate, "concatenate", 1, 0, 0,
269
"Construct a list by appending all lists in @var{lstlst}.\n"
271
"@code{concatenate} is the same as @code{(apply append\n"
272
"@var{lstlst})}. It exists because some Scheme implementations\n"
273
"have a limit on the number of arguments a function takes, which\n"
274
"the @code{apply} might exceed. In Guile there is no such\n"
276
#define FUNC_NAME s_scm_srfi1_concatenate
278
SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
279
return scm_append (lstlst);
284
SCM_DEFINE (scm_srfi1_concatenate_x, "concatenate!", 1, 0, 0,
286
"Construct a list by appending all lists in @var{lstlst}. Those\n"
287
"lists may be modified to produce the result.\n"
289
"@code{concatenate!} is the same as @code{(apply append!\n"
290
"@var{lstlst})}. It exists because some Scheme implementations\n"
291
"have a limit on the number of arguments a function takes, which\n"
292
"the @code{apply} might exceed. In Guile there is no such\n"
294
#define FUNC_NAME s_scm_srfi1_concatenate
296
SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
297
return scm_append_x (lstlst);
302
SCM_DEFINE (scm_srfi1_count, "count", 2, 0, 1,
303
(SCM pred, SCM list1, SCM rest),
304
"Return a count of the number of times @var{pred} returns true\n"
305
"when called on elements from the given lists.\n"
307
"@var{pred} is called with @var{N} parameters @code{(@var{pred}\n"
308
"@var{elem1} @dots{} @var{elemN})}, each element being from the\n"
309
"corresponding @var{list1} @dots{} @var{lstN}. The first call is\n"
310
"with the first element of each list, the second with the second\n"
311
"element from each, and so on.\n"
313
"Counting stops when the end of the shortest list is reached.\n"
314
"At least one list must be non-circular.")
315
#define FUNC_NAME s_scm_srfi1_count
320
SCM_VALIDATE_REST_ARGUMENT (rest);
324
if (scm_is_null (rest))
327
scm_t_trampoline_1 pred_tramp;
328
pred_tramp = scm_trampoline_1 (pred);
329
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
331
for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1))
332
count += scm_is_true (pred_tramp (pred, SCM_CAR (list1)));
334
/* check below that list1 is a proper list, and done */
339
else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest)))
342
scm_t_trampoline_2 pred_tramp;
345
pred_tramp = scm_trampoline_2 (pred);
346
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
348
list2 = SCM_CAR (rest);
351
if (! scm_is_pair (list1))
353
if (! scm_is_pair (list2))
359
count += scm_is_true (pred_tramp
360
(pred, SCM_CAR (list1), SCM_CAR (list2)));
361
list1 = SCM_CDR (list1);
362
list2 = SCM_CDR (list2);
367
/* three or more lists */
371
/* vec is the list arguments */
372
vec = scm_vector (scm_cons (list1, rest));
373
len = SCM_SIMPLE_VECTOR_LENGTH (vec);
375
/* args is the argument list to pass to pred, same length as vec,
376
re-used for each call */
377
args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED);
381
/* first elem of each list in vec into args, and step those
382
vec entries onto their next element */
383
for (i = 0, a = args, argnum = 2;
385
i++, a = SCM_CDR (a), argnum++)
387
lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */
388
if (! scm_is_pair (lst))
389
goto check_lst_and_done;
390
SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */
391
SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */
394
count += scm_is_true (scm_apply (pred, args, SCM_EOL));
399
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list");
400
return scm_from_long (count);
405
SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0,
406
(SCM x, SCM lst, SCM pred),
407
"Return a list containing the elements of @var{lst} but with\n"
408
"those equal to @var{x} deleted. The returned elements will be\n"
409
"in the same order as they were in @var{lst}.\n"
411
"Equality is determined by @var{pred}, or @code{equal?} if not\n"
412
"given. An equality call is made just once for each element,\n"
413
"but the order in which the calls are made on the elements is\n"
416
"The equality calls are always @code{(pred x elem)}, ie.@: the\n"
417
"given @var{x} is first. This means for instance elements\n"
418
"greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
420
"@var{lst} is not modified, but the returned list might share a\n"
421
"common tail with @var{lst}.")
422
#define FUNC_NAME s_scm_srfi1_delete
424
scm_t_trampoline_2 equal_p;
425
SCM ret, *p, keeplst;
428
if (SCM_UNBNDP (pred))
429
return scm_delete (x, lst);
431
equal_p = scm_trampoline_2 (pred);
432
SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME);
434
/* ret is the return list being constructed. p is where to append to it,
435
initially &ret then SCM_CDRLOC of the last pair. lst progresses as
436
elements are considered.
438
Elements to be retained are not immediately copied, instead keeplst is
439
the last pair in lst which is to be retained but not yet copied, count
440
is how many from there are wanted. When there's no more deletions, *p
441
can be set to keeplst to share the remainder of the original lst. (The
442
entire original lst if there's no deletions at all.) */
448
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
450
if (scm_is_true (equal_p (pred, x, SCM_CAR (lst))))
452
/* delete this element, so copy those at keeplst */
453
p = list_copy_part (keeplst, count, p);
454
keeplst = SCM_CDR (lst);
459
/* keep this element */
464
/* final retained elements */
467
/* demand that lst was a proper list */
468
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
475
SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0,
476
(SCM x, SCM lst, SCM pred),
477
"Return a list containing the elements of @var{lst} but with\n"
478
"those equal to @var{x} deleted. The returned elements will be\n"
479
"in the same order as they were in @var{lst}.\n"
481
"Equality is determined by @var{pred}, or @code{equal?} if not\n"
482
"given. An equality call is made just once for each element,\n"
483
"but the order in which the calls are made on the elements is\n"
486
"The equality calls are always @code{(pred x elem)}, ie.@: the\n"
487
"given @var{x} is first. This means for instance elements\n"
488
"greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
490
"@var{lst} may be modified to construct the returned list.")
491
#define FUNC_NAME s_scm_srfi1_delete_x
493
scm_t_trampoline_2 equal_p;
497
if (SCM_UNBNDP (pred))
498
return scm_delete_x (x, lst);
500
equal_p = scm_trampoline_2 (pred);
501
SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME);
503
for (prev = &lst, walk = lst;
505
walk = SCM_CDR (walk))
507
if (scm_is_true (equal_p (pred, x, SCM_CAR (walk))))
508
*prev = SCM_CDR (walk);
510
prev = SCM_CDRLOC (walk);
513
/* demand the input was a proper list */
514
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list");
520
SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0,
522
"Return a list containing the elements of @var{lst} but without\n"
525
"When elements are equal, only the first in @var{lst} is\n"
526
"retained. Equal elements can be anywhere in @var{lst}, they\n"
527
"don't have to be adjacent. The returned list will have the\n"
528
"retained elements in the same order as they were in @var{lst}.\n"
530
"Equality is determined by @var{pred}, or @code{equal?} if not\n"
531
"given. Calls @code{(pred x y)} are made with element @var{x}\n"
532
"being before @var{y} in @var{lst}. A call is made at most once\n"
533
"for each combination, but the sequence of the calls across the\n"
534
"elements is unspecified.\n"
536
"@var{lst} is not modified, but the return might share a common\n"
537
"tail with @var{lst}.\n"
539
"In the worst case, this is an @math{O(N^2)} algorithm because\n"
540
"it must check each element against all those preceding it. For\n"
541
"long lists it is more efficient to sort and then compare only\n"
542
"adjacent elements.")
543
#define FUNC_NAME s_scm_srfi1_delete_duplicates
545
scm_t_trampoline_2 equal_p;
546
SCM ret, *p, keeplst, item, l;
549
/* ret is the new list constructed. p is where to append, initially &ret
550
then SCM_CDRLOC of the last pair. lst is advanced as each element is
553
Elements retained are not immediately appended to ret, instead keeplst
554
is the last pair in lst which is to be kept but is not yet copied.
555
Initially this is the first pair of lst, since the first element is
558
*p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all
559
the elements retained, making the equality search loop easy.
561
If an item must be deleted, elements from keeplst (inclusive) to lst
562
(exclusive) must be copied and appended to ret. When there's no more
563
deletions, *p is left set to keeplst, so ret shares structure with the
564
original lst. (ret will be the entire original lst if there are no
567
/* skip to end if an empty list (or something invalid) */
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);
582
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
584
item = SCM_CAR (lst);
586
/* look for item in "ret" list */
587
for (l = ret; scm_is_pair (l); l = SCM_CDR (l))
589
if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
591
/* "item" is a duplicate, so copy keeplst onto ret */
593
p = list_copy_part (keeplst, count, p);
595
keeplst = SCM_CDR (lst); /* elem after the one deleted */
601
/* look for item in "keeplst" list
602
be careful traversing, in case nasty code changed the cdrs */
603
for (i = 0, l = keeplst;
604
i < count && scm_is_pair (l);
605
i++, l = SCM_CDR (l))
606
if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
609
/* keep this element */
615
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list");
617
/* share tail of keeplst items */
625
SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0,
627
"Return a list containing the elements of @var{lst} but without\n"
630
"When elements are equal, only the first in @var{lst} is\n"
631
"retained. Equal elements can be anywhere in @var{lst}, they\n"
632
"don't have to be adjacent. The returned list will have the\n"
633
"retained elements in the same order as they were in @var{lst}.\n"
635
"Equality is determined by @var{pred}, or @code{equal?} if not\n"
636
"given. Calls @code{(pred x y)} are made with element @var{x}\n"
637
"being before @var{y} in @var{lst}. A call is made at most once\n"
638
"for each combination, but the sequence of the calls across the\n"
639
"elements is unspecified.\n"
641
"@var{lst} may be modified to construct the returned list.\n"
643
"In the worst case, this is an @math{O(N^2)} algorithm because\n"
644
"it must check each element against all those preceding it. For\n"
645
"long lists it is more efficient to sort and then compare only\n"
646
"adjacent elements.")
647
#define FUNC_NAME s_scm_srfi1_delete_duplicates_x
649
scm_t_trampoline_2 equal_p;
650
SCM ret, endret, item, l;
652
/* ret is the return list, constructed from the pairs in lst. endret is
653
the last pair of ret, initially the first pair. lst is advanced as
654
elements are considered. */
656
/* skip to end if an empty list (or something invalid) */
658
if (scm_is_pair (lst))
660
if (SCM_UNBNDP (pred))
661
equal_p = equal_trampoline;
664
equal_p = scm_trampoline_2 (pred);
665
SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME);
670
/* loop over lst elements starting from second */
674
if (! scm_is_pair (lst))
676
item = SCM_CAR (lst);
678
/* is item equal to any element from ret to endret (inclusive)? */
682
if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
683
break; /* equal, forget this element */
685
if (scm_is_eq (l, endret))
687
/* not equal to any, so append this pair */
688
SCM_SETCDR (endret, lst);
696
/* terminate, in case last element was deleted */
697
SCM_SETCDR (endret, SCM_EOL);
700
/* demand that lst was a proper list */
701
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list");
708
SCM_DEFINE (scm_srfi1_drop_right, "drop-right", 2, 0, 0,
710
"Return a new list containing all except the last @var{n}\n"
711
"elements of @var{lst}.")
712
#define FUNC_NAME s_scm_srfi1_drop_right
714
SCM tail = scm_list_tail (lst, n);
717
while (scm_is_pair (tail))
719
*rend = scm_cons (SCM_CAR (lst), SCM_EOL);
720
rend = SCM_CDRLOC (*rend);
723
tail = SCM_CDR (tail);
725
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list");
731
SCM_DEFINE (scm_srfi1_drop_right_x, "drop-right!", 2, 0, 0,
733
"Return the a list containing the @var{n} last elements of\n"
734
"@var{lst}. @var{lst} may be modified to build the return.")
735
#define FUNC_NAME s_scm_srfi1_drop_right_x
739
if (scm_is_eq (n, SCM_INUM0))
742
tail = scm_list_tail (lst, n);
745
/* p and tail work along the list, p being the cdrloc of the cell n steps
747
for ( ; scm_is_pair (tail); tail = SCM_CDR (tail))
750
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list");
758
SCM_DEFINE (scm_srfi1_drop_while, "drop-while", 2, 0, 0,
760
"Drop the longest initial prefix of @var{lst} whose elements all\n"
761
"satisfy the predicate @var{pred}.")
762
#define FUNC_NAME s_scm_srfi1_drop_while
764
scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred);
765
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
767
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
768
if (scm_is_false (pred_tramp (pred, SCM_CAR (lst))))
771
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
778
SCM_DEFINE (scm_srfi1_eighth, "eighth", 1, 0, 0,
780
"Return the eighth element of @var{lst}.")
781
#define FUNC_NAME s_scm_srfi1_eighth
783
return scm_list_ref (lst, SCM_I_MAKINUM (7));
788
SCM_DEFINE (scm_srfi1_fifth, "fifth", 1, 0, 0,
790
"Return the fifth element of @var{lst}.")
791
#define FUNC_NAME s_scm_srfi1_fifth
793
return scm_list_ref (lst, SCM_I_MAKINUM (4));
798
SCM_DEFINE (scm_srfi1_filter_map, "filter-map", 2, 0, 1,
799
(SCM proc, SCM list1, SCM rest),
800
"Apply @var{proc} to to the elements of @var{list1} @dots{} and\n"
801
"return a list of the results as per SRFI-1 @code{map}, except\n"
802
"that any @code{#f} results are omitted from the list returned.")
803
#define FUNC_NAME s_scm_srfi1_filter_map
805
SCM ret, *loc, elem, newcell, lst;
808
SCM_VALIDATE_REST_ARGUMENT (rest);
813
if (scm_is_null (rest))
816
scm_t_trampoline_1 proc_tramp = scm_trampoline_1 (proc);
817
SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME);
819
for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1))
821
elem = proc_tramp (proc, SCM_CAR (list1));
822
if (scm_is_true (elem))
824
newcell = scm_cons (elem, SCM_EOL);
826
loc = SCM_CDRLOC (newcell);
830
/* check below that list1 is a proper list, and done */
835
else if (scm_is_null (SCM_CDR (rest)))
838
scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc);
839
SCM list2 = SCM_CAR (rest);
840
SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME);
844
if (! scm_is_pair (list1))
846
if (! scm_is_pair (list2))
850
goto check_lst_and_done;
852
elem = proc_tramp (proc, SCM_CAR (list1), SCM_CAR (list2));
853
if (scm_is_true (elem))
855
newcell = scm_cons (elem, SCM_EOL);
857
loc = SCM_CDRLOC (newcell);
859
list1 = SCM_CDR (list1);
860
list2 = SCM_CDR (list2);
865
/* three or more lists */
869
/* vec is the list arguments */
870
vec = scm_vector (scm_cons (list1, rest));
871
len = SCM_SIMPLE_VECTOR_LENGTH (vec);
873
/* args is the argument list to pass to proc, same length as vec,
874
re-used for each call */
875
args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED);
879
/* first elem of each list in vec into args, and step those
880
vec entries onto their next element */
881
for (i = 0, a = args, argnum = 2;
883
i++, a = SCM_CDR (a), argnum++)
885
lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */
886
if (! scm_is_pair (lst))
887
goto check_lst_and_done;
888
SCM_SETCAR (a, SCM_CAR (lst)); /* arg for proc */
889
SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */
892
elem = scm_apply (proc, args, SCM_EOL);
893
if (scm_is_true (elem))
895
newcell = scm_cons (elem, SCM_EOL);
897
loc = SCM_CDRLOC (newcell);
903
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list");
909
SCM_DEFINE (scm_srfi1_find, "find", 2, 0, 0,
911
"Return the first element of @var{lst} which satisfies the\n"
912
"predicate @var{pred}, or return @code{#f} if no such element is\n"
914
#define FUNC_NAME s_scm_srfi1_find
916
scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred);
917
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
919
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
921
SCM elem = SCM_CAR (lst);
922
if (scm_is_true (pred_tramp (pred, elem)))
925
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
932
SCM_DEFINE (scm_srfi1_find_tail, "find-tail", 2, 0, 0,
934
"Return the first pair of @var{lst} whose @sc{car} satisfies the\n"
935
"predicate @var{pred}, or return @code{#f} if no such element is\n"
937
#define FUNC_NAME s_scm_srfi1_find_tail
939
scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred);
940
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
942
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
943
if (scm_is_true (pred_tramp (pred, SCM_CAR (lst))))
945
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
952
SCM_DEFINE (scm_srfi1_fold, "fold", 3, 0, 1,
953
(SCM proc, SCM init, SCM list1, SCM rest),
954
"Apply @var{proc} to the elements of @var{lst1} @dots{}\n"
955
"@var{lstN} to build a result, and return that result.\n"
957
"Each @var{proc} call is @code{(@var{proc} @var{elem1} @dots{}\n"
958
"@var{elemN} @var{previous})}, where @var{elem1} is from\n"
959
"@var{lst1}, through @var{elemN} from @var{lstN}.\n"
960
"@var{previous} is the return from the previous call to\n"
961
"@var{proc}, or the given @var{init} for the first call. If any\n"
962
"list is empty, just @var{init} is returned.\n"
964
"@code{fold} works through the list elements from first to last.\n"
965
"The following shows a list reversal and the calls it makes,\n"
968
"(fold cons '() '(1 2 3))\n"
973
"@result{} (3 2 1)\n"
976
"If @var{lst1} through @var{lstN} have different lengths,\n"
977
"@code{fold} stops when the end of the shortest is reached.\n"
978
"Ie.@: elements past the length of the shortest are ignored in\n"
979
"the other @var{lst}s. At least one @var{lst} must be\n"
982
"The way @code{fold} builds a result from iterating is quite\n"
983
"general, it can do more than other iterations like say\n"
984
"@code{map} or @code{filter}. The following for example removes\n"
985
"adjacent duplicate elements from a list,\n"
988
"(define (delete-adjacent-duplicates lst)\n"
989
" (fold-right (lambda (elem ret)\n"
990
" (if (equal? elem (first ret))\n"
992
" (cons elem ret)))\n"
993
" (list (last lst))\n"
995
"(delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))\n"
996
"@result{} (1 2 3 4 5)\n"
999
"Clearly the same sort of thing can be done with a\n"
1000
"@code{for-each} and a variable in which to build the result,\n"
1001
"but a self-contained @var{proc} can be re-used in multiple\n"
1002
"contexts, where a @code{for-each} would have to be written out\n"
1004
#define FUNC_NAME s_scm_srfi1_fold
1008
SCM_VALIDATE_REST_ARGUMENT (rest);
1010
if (scm_is_null (rest))
1013
scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc);
1014
SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME);
1016
for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1))
1017
init = proc_tramp (proc, SCM_CAR (list1), init);
1019
/* check below that list1 is a proper list, and done */
1025
/* two or more lists */
1029
/* vec is the list arguments */
1030
vec = scm_vector (scm_cons (list1, rest));
1031
len = SCM_SIMPLE_VECTOR_LENGTH (vec);
1033
/* args is the argument list to pass to proc, same length as vec,
1034
re-used for each call */
1035
args = scm_make_list (SCM_I_MAKINUM (len+1), SCM_UNDEFINED);
1039
/* first elem of each list in vec into args, and step those
1040
vec entries onto their next element */
1041
for (i = 0, a = args, argnum = 2;
1043
i++, a = SCM_CDR (a), argnum++)
1045
lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */
1046
if (! scm_is_pair (lst))
1047
goto check_lst_and_done;
1048
SCM_SETCAR (a, SCM_CAR (lst)); /* arg for proc */
1049
SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */
1051
SCM_SETCAR (a, init);
1053
init = scm_apply (proc, args, SCM_EOL);
1058
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list");
1064
SCM_DEFINE (scm_srfi1_last, "last", 1, 0, 0,
1066
"Like @code{cons}, but with interchanged arguments. Useful\n"
1067
"mostly when passed to higher-order procedures.")
1068
#define FUNC_NAME s_scm_srfi1_last
1070
SCM pair = scm_last_pair (lst);
1071
/* scm_last_pair returns SCM_EOL for an empty list */
1072
SCM_VALIDATE_CONS (SCM_ARG1, pair);
1073
return SCM_CAR (pair);
1078
SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0,
1080
"Return the length of @var{lst}, or @code{#f} if @var{lst} is\n"
1082
#define FUNC_NAME s_scm_srfi1_length_plus
1084
long len = scm_ilength (lst);
1085
return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F);
1090
SCM_DEFINE (scm_srfi1_list_index, "list-index", 2, 0, 1,
1091
(SCM pred, SCM list1, SCM rest),
1092
"Return the index of the first set of elements, one from each of\n"
1093
"@var{lst1}@dots{}@var{lstN}, which satisfies @var{pred}.\n"
1095
"@var{pred} is called as @code{(@var{pred} elem1 @dots{}\n"
1096
"elemN)}. Searching stops when the end of the shortest\n"
1097
"@var{lst} is reached. The return index starts from 0 for the\n"
1098
"first set of elements. If no set of elements pass then the\n"
1099
"return is @code{#f}.\n"
1102
"(list-index odd? '(2 4 6 9)) @result{} 3\n"
1103
"(list-index = '(1 2 3) '(3 1 2)) @result{} #f\n"
1105
#define FUNC_NAME s_scm_srfi1_list_index
1110
SCM_VALIDATE_REST_ARGUMENT (rest);
1112
if (scm_is_null (rest))
1115
scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred);
1116
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
1118
for ( ; scm_is_pair (list1); n++, list1 = SCM_CDR (list1))
1119
if (scm_is_true (pred_tramp (pred, SCM_CAR (list1))))
1120
return SCM_I_MAKINUM (n);
1122
/* not found, check below that list1 is a proper list */
1127
else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest)))
1130
SCM list2 = SCM_CAR (rest);
1131
scm_t_trampoline_2 pred_tramp = scm_trampoline_2 (pred);
1132
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
1136
if (! scm_is_pair (list1))
1138
if (! scm_is_pair (list2))
1144
if (scm_is_true (pred_tramp (pred,
1145
SCM_CAR (list1), SCM_CAR (list2))))
1146
return SCM_I_MAKINUM (n);
1148
list1 = SCM_CDR (list1);
1149
list2 = SCM_CDR (list2);
1154
/* three or more lists */
1158
/* vec is the list arguments */
1159
vec = scm_vector (scm_cons (list1, rest));
1160
len = SCM_SIMPLE_VECTOR_LENGTH (vec);
1162
/* args is the argument list to pass to pred, same length as vec,
1163
re-used for each call */
1164
args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED);
1168
/* first elem of each list in vec into args, and step those
1169
vec entries onto their next element */
1170
for (i = 0, a = args, argnum = 2;
1172
i++, a = SCM_CDR (a), argnum++)
1174
lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */
1175
if (! scm_is_pair (lst))
1176
goto not_found_check_lst;
1177
SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */
1178
SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */
1181
if (scm_is_true (scm_apply (pred, args, SCM_EOL)))
1182
return SCM_I_MAKINUM (n);
1186
not_found_check_lst:
1187
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list");
1193
/* This routine differs from the core list-copy in allowing improper lists.
1194
Maybe the core could allow them similarly. */
1196
SCM_DEFINE (scm_srfi1_list_copy, "list-copy", 1, 0, 0,
1198
"Return a copy of the given list @var{lst}.\n"
1200
"@var{lst} can be a proper or improper list. And if @var{lst}\n"
1201
"is not a pair then it's treated as the final tail of an\n"
1202
"improper list and simply returned.")
1203
#define FUNC_NAME s_scm_srfi1_list_copy
1210
fill_here = &newlst;
1213
while (scm_is_pair (from_here))
1216
c = scm_cons (SCM_CAR (from_here), SCM_CDR (from_here));
1218
fill_here = SCM_CDRLOC (c);
1219
from_here = SCM_CDR (from_here);
1226
SCM_DEFINE (scm_srfi1_list_tabulate, "list-tabulate", 2, 0, 0,
1228
"Return an @var{n}-element list, where each list element is\n"
1229
"produced by applying the procedure @var{init-proc} to the\n"
1230
"corresponding list index. The order in which @var{init-proc}\n"
1231
"is applied to the indices is not specified.")
1232
#define FUNC_NAME s_scm_srfi1_list_tabulate
1235
scm_t_trampoline_1 proc_tramp = scm_trampoline_1 (proc);
1238
nn = scm_to_signed_integer (n, 0, LONG_MAX);
1239
SCM_ASSERT (proc_tramp, proc, SCM_ARG2, FUNC_NAME);
1241
for (i = nn-1; i >= 0; i--)
1242
ret = scm_cons (proc_tramp (proc, scm_from_long (i)), ret);
1249
SCM_DEFINE (scm_srfi1_lset_adjoin, "lset-adjoin", 2, 0, 1,
1250
(SCM equal, SCM lst, SCM rest),
1251
"Add to @var{list} any of the given @var{elem}s not already in\n"
1252
"the list. @var{elem}s are @code{cons}ed onto the start of\n"
1253
"@var{list} (so the return shares a common tail with\n"
1254
"@var{list}), but the order they're added is unspecified.\n"
1256
"The given @var{=} procedure is used for comparing elements,\n"
1257
"called as @code{(@var{=} listelem elem)}, ie.@: the second\n"
1258
"argument is one of the given @var{elem} parameters.\n"
1261
"(lset-adjoin eqv? '(1 2 3) 4 1 5) @result{} (5 4 1 2 3)\n"
1263
#define FUNC_NAME s_scm_srfi1_lset_adjoin
1265
scm_t_trampoline_2 equal_tramp;
1268
equal_tramp = scm_trampoline_2 (equal);
1269
SCM_ASSERT (equal_tramp, equal, SCM_ARG1, FUNC_NAME);
1270
SCM_VALIDATE_REST_ARGUMENT (rest);
1272
/* It's not clear if duplicates among the `rest' elements are meant to be
1273
cast out. The spec says `=' is called as (= list-elem rest-elem),
1274
suggesting perhaps not, but the reference implementation shows the
1275
"list" at each stage as including those "rest" elements already added.
1276
The latter corresponds to what's described for lset-union, so that's
1277
what's done here. */
1279
for ( ; scm_is_pair (rest); rest = SCM_CDR (rest))
1281
elem = SCM_CAR (rest);
1283
for (l = lst; scm_is_pair (l); l = SCM_CDR (l))
1284
if (scm_is_true (equal_tramp (equal, SCM_CAR (l), elem)))
1285
goto next_elem; /* elem already in lst, don't add */
1287
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(l), lst, SCM_ARG2, FUNC_NAME, "list");
1289
/* elem is not equal to anything already in lst, add it */
1290
lst = scm_cons (elem, lst);
1301
SCM_DEFINE (scm_srfi1_lset_difference_x, "lset-difference!", 2, 0, 1,
1302
(SCM equal, SCM lst, SCM rest),
1303
"Return @var{lst} with any elements in the lists in @var{rest}\n"
1304
"removed (ie.@: subtracted). For only one @var{lst} argument,\n"
1305
"just that list is returned.\n"
1307
"The given @var{equal} procedure is used for comparing elements,\n"
1308
"called as @code{(@var{equal} elem1 elemN)}. The first argument\n"
1309
"is from @var{lst} and the second from one of the subsequent\n"
1310
"lists. But exactly which calls are made and in what order is\n"
1314
"(lset-difference! eqv? (list 'x 'y)) @result{} (x y)\n"
1315
"(lset-difference! eqv? (list 1 2 3) '(3 1)) @result{} (2)\n"
1316
"(lset-difference! eqv? (list 1 2 3) '(3) '(2)) @result{} (1)\n"
1319
"@code{lset-difference!} may modify @var{lst} to form its\n"
1321
#define FUNC_NAME s_scm_srfi1_lset_difference_x
1323
scm_t_trampoline_2 equal_tramp = scm_trampoline_2 (equal);
1324
SCM ret, *pos, elem, r, b;
1327
SCM_ASSERT (equal_tramp, equal, SCM_ARG1, FUNC_NAME);
1328
SCM_VALIDATE_REST_ARGUMENT (rest);
1332
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
1334
elem = SCM_CAR (lst);
1336
for (r = rest, argnum = SCM_ARG3;
1338
r = SCM_CDR (r), argnum++)
1340
for (b = SCM_CAR (r); scm_is_pair (b); b = SCM_CDR (b))
1341
if (scm_is_true (equal_tramp (equal, elem, SCM_CAR (b))))
1342
goto next_elem; /* equal to elem, so drop that elem */
1344
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (b), b, argnum, FUNC_NAME,"list");
1347
/* elem not equal to anything in later lists, so keep it */
1349
pos = SCM_CDRLOC (lst);
1354
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
1362
/* Typechecking for multi-argument MAP and FOR-EACH.
1364
Verify that each element of the vector ARGV, except for the first,
1365
is a list and return minimum length. Attribute errors to WHO,
1366
and claim that the i'th element of ARGV is WHO's i+2'th argument. */
1368
check_map_args (SCM argv,
1378
for (i = SCM_SIMPLE_VECTOR_LENGTH (argv) - 1; i >= 1; i--)
1381
elt = SCM_SIMPLE_VECTOR_REF (argv, i);
1383
if (!(scm_is_null (elt) || scm_is_pair (elt)))
1384
goto check_map_error;
1386
elt_len = srfi1_ilength (elt);
1388
goto check_map_error;
1390
if (len < 0 || (elt_len >= 0 && elt_len < len))
1400
scm_apply_generic (gf, scm_cons (proc, args));
1402
scm_wrong_type_arg (who, i + 2, elt);
1405
scm_remember_upto_here_1 (argv);
1410
SCM_GPROC (s_srfi1_map, "map", 2, 0, 1, scm_srfi1_map, g_srfi1_map);
1412
/* Note: Currently, scm_srfi1_map applies PROC to the argument list(s)
1413
sequentially, starting with the first element(s). This is used in
1414
the Scheme procedure `map-in-order', which guarantees sequential
1415
behaviour, is implemented using scm_map. If the behaviour changes,
1416
we need to update `map-in-order'.
1420
scm_srfi1_map (SCM proc, SCM arg1, SCM args)
1421
#define FUNC_NAME s_srfi1_map
1427
len = srfi1_ilength (arg1);
1428
SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1,
1430
scm_cons2 (proc, arg1, args), SCM_ARG2, s_srfi1_map);
1431
SCM_VALIDATE_REST_ARGUMENT (args);
1432
if (scm_is_null (args))
1434
scm_t_trampoline_1 call = scm_trampoline_1 (proc);
1435
SCM_GASSERT2 (call, g_srfi1_map, proc, arg1, SCM_ARG1, s_srfi1_map);
1436
SCM_GASSERT2 (len >= 0, g_srfi1_map, proc, arg1, SCM_ARG2, s_srfi1_map);
1437
while (SCM_NIMP (arg1))
1439
*pres = scm_list_1 (call (proc, SCM_CAR (arg1)));
1440
pres = SCM_CDRLOC (*pres);
1441
arg1 = SCM_CDR (arg1);
1445
if (scm_is_null (SCM_CDR (args)))
1447
SCM arg2 = SCM_CAR (args);
1448
int len2 = srfi1_ilength (arg2);
1449
scm_t_trampoline_2 call = scm_trampoline_2 (proc);
1450
SCM_GASSERTn (call, g_srfi1_map,
1451
scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_map);
1452
if (len < 0 || (len2 >= 0 && len2 < len))
1454
SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2))
1455
&& len >= 0 && len2 >= -1,
1457
scm_cons2 (proc, arg1, args),
1458
len2 >= 0 ? SCM_ARG2 : SCM_ARG3,
1462
*pres = scm_list_1 (call (proc, SCM_CAR (arg1), SCM_CAR (arg2)));
1463
pres = SCM_CDRLOC (*pres);
1464
arg1 = SCM_CDR (arg1);
1465
arg2 = SCM_CDR (arg2);
1470
args = scm_vector (arg1 = scm_cons (arg1, args));
1471
len = check_map_args (args, len, g_srfi1_map, proc, arg1, s_srfi1_map);
1475
for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--)
1477
SCM elt = SCM_SIMPLE_VECTOR_REF (args, i);
1478
arg1 = scm_cons (SCM_CAR (elt), arg1);
1479
SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt));
1481
*pres = scm_list_1 (scm_apply (proc, arg1, SCM_EOL));
1482
pres = SCM_CDRLOC (*pres);
1489
SCM_REGISTER_PROC (s_srfi1_map_in_order, "map-in-order", 2, 0, 1, scm_srfi1_map);
1491
SCM_GPROC (s_srfi1_for_each, "for-each", 2, 0, 1, scm_srfi1_for_each, g_srfi1_for_each);
1494
scm_srfi1_for_each (SCM proc, SCM arg1, SCM args)
1495
#define FUNC_NAME s_srfi1_for_each
1498
len = srfi1_ilength (arg1);
1499
SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1,
1500
g_srfi1_for_each, scm_cons2 (proc, arg1, args),
1501
SCM_ARG2, s_srfi1_for_each);
1502
SCM_VALIDATE_REST_ARGUMENT (args);
1503
if (scm_is_null (args))
1505
scm_t_trampoline_1 call = scm_trampoline_1 (proc);
1506
SCM_GASSERT2 (call, g_srfi1_for_each, proc, arg1,
1507
SCM_ARG1, s_srfi1_for_each);
1508
SCM_GASSERT2 (len >= 0, g_srfi1_for_each, proc, arg1,
1509
SCM_ARG2, s_srfi1_map);
1510
while (SCM_NIMP (arg1))
1512
call (proc, SCM_CAR (arg1));
1513
arg1 = SCM_CDR (arg1);
1515
return SCM_UNSPECIFIED;
1517
if (scm_is_null (SCM_CDR (args)))
1519
SCM arg2 = SCM_CAR (args);
1520
int len2 = srfi1_ilength (arg2);
1521
scm_t_trampoline_2 call = scm_trampoline_2 (proc);
1522
SCM_GASSERTn (call, g_srfi1_for_each,
1523
scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_for_each);
1524
if (len < 0 || (len2 >= 0 && len2 < len))
1526
SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2))
1527
&& len >= 0 && len2 >= -1,
1529
scm_cons2 (proc, arg1, args),
1530
len2 >= 0 ? SCM_ARG2 : SCM_ARG3,
1534
call (proc, SCM_CAR (arg1), SCM_CAR (arg2));
1535
arg1 = SCM_CDR (arg1);
1536
arg2 = SCM_CDR (arg2);
1539
return SCM_UNSPECIFIED;
1541
args = scm_vector (arg1 = scm_cons (arg1, args));
1542
len = check_map_args (args, len, g_srfi1_for_each, proc, arg1,
1547
for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--)
1549
SCM elt = SCM_SIMPLE_VECTOR_REF (args, i);
1550
arg1 = scm_cons (SCM_CAR (elt), arg1);
1551
SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt));
1553
scm_apply (proc, arg1, SCM_EOL);
1556
return SCM_UNSPECIFIED;
1561
SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0,
1562
(SCM x, SCM lst, SCM pred),
1563
"Return the first sublist of @var{lst} whose @sc{car} is equal\n"
1564
"to @var{x}. If @var{x} does not appear in @var{lst}, return\n"
1567
"Equality is determined by @code{equal?}, or by the equality\n"
1568
"predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n"
1569
"elem)}, ie.@: with the given @var{x} first, so for example to\n"
1570
"find the first element greater than 5,\n"
1573
"(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n"
1576
"This version of @code{member} extends the core @code{member} by\n"
1577
"accepting an equality predicate.")
1578
#define FUNC_NAME s_scm_srfi1_member
1580
scm_t_trampoline_2 equal_p;
1581
SCM_VALIDATE_LIST (2, lst);
1582
if (SCM_UNBNDP (pred))
1583
equal_p = equal_trampoline;
1586
equal_p = scm_trampoline_2 (pred);
1587
SCM_ASSERT (equal_p, pred, 3, FUNC_NAME);
1589
for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
1591
if (scm_is_true (equal_p (pred, x, SCM_CAR (lst))))
1598
SCM_DEFINE (scm_srfi1_assoc, "assoc", 2, 1, 0,
1599
(SCM key, SCM alist, SCM pred),
1600
"Behaves like @code{assq} but uses third argument @var{pred?}\n"
1601
"for key comparison. If @var{pred?} is not supplied,\n"
1602
"@code{equal?} is used. (Extended from R5RS.)\n")
1603
#define FUNC_NAME s_scm_srfi1_assoc
1606
scm_t_trampoline_2 equal_p;
1607
if (SCM_UNBNDP (pred))
1608
equal_p = equal_trampoline;
1611
equal_p = scm_trampoline_2 (pred);
1612
SCM_ASSERT (equal_p, pred, 3, FUNC_NAME);
1614
for(; scm_is_pair (ls); ls = SCM_CDR (ls))
1616
SCM tmp = SCM_CAR (ls);
1617
SCM_ASSERT_TYPE (scm_is_pair (tmp), alist, SCM_ARG2, FUNC_NAME,
1618
"association list");
1619
if (scm_is_true (equal_p (pred, key, SCM_CAR (tmp))))
1622
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls), alist, SCM_ARG2, FUNC_NAME,
1623
"association list");
1629
SCM_DEFINE (scm_srfi1_ninth, "ninth", 1, 0, 0,
1631
"Return the ninth element of @var{lst}.")
1632
#define FUNC_NAME s_scm_srfi1_ninth
1634
return scm_list_ref (lst, scm_from_int (8));
1639
SCM_DEFINE (scm_srfi1_not_pair_p, "not-pair?", 1, 0, 0,
1641
"Return @code{#t} is @var{obj} is not a pair, @code{#f}\n"
1644
"This is shorthand notation @code{(not (pair? @var{obj}))} and\n"
1645
"is supposed to be used for end-of-list checking in contexts\n"
1646
"where dotted lists are allowed.")
1647
#define FUNC_NAME s_scm_srfi1_not_pair_p
1649
return scm_from_bool (! scm_is_pair (obj));
1654
SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0,
1655
(SCM pred, SCM list),
1656
"Partition the elements of @var{list} with predicate @var{pred}.\n"
1657
"Return two values: the list of elements satifying @var{pred} and\n"
1658
"the list of elements @emph{not} satisfying @var{pred}. The order\n"
1659
"of the output lists follows the order of @var{list}. @var{list}\n"
1660
"is not mutated. One of the output lists may share memory with @var{list}.\n")
1661
#define FUNC_NAME s_scm_srfi1_partition
1663
/* In this implementation, the output lists don't share memory with
1664
list, because it's probably not worth the effort. */
1665
scm_t_trampoline_1 call = scm_trampoline_1(pred);
1666
SCM kept = scm_cons(SCM_EOL, SCM_EOL);
1667
SCM kept_tail = kept;
1668
SCM dropped = scm_cons(SCM_EOL, SCM_EOL);
1669
SCM dropped_tail = dropped;
1671
SCM_ASSERT(call, pred, 2, FUNC_NAME);
1673
for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) {
1674
SCM elt = SCM_CAR(list);
1675
SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL);
1676
if (scm_is_true (call (pred, elt))) {
1677
SCM_SETCDR(kept_tail, new_tail);
1678
kept_tail = new_tail;
1681
SCM_SETCDR(dropped_tail, new_tail);
1682
dropped_tail = new_tail;
1685
/* re-use the initial conses for the values list */
1686
SCM_SETCAR(kept, SCM_CDR(kept));
1687
SCM_SETCDR(kept, dropped);
1688
SCM_SETCAR(dropped, SCM_CDR(dropped));
1689
SCM_SETCDR(dropped, SCM_EOL);
1690
return scm_values(kept);
1695
SCM_DEFINE (scm_srfi1_partition_x, "partition!", 2, 0, 0,
1696
(SCM pred, SCM lst),
1697
"Split @var{lst} into those elements which do and don't satisfy\n"
1698
"the predicate @var{pred}.\n"
1700
"The return is two values (@pxref{Multiple Values}), the first\n"
1701
"being a list of all elements from @var{lst} which satisfy\n"
1702
"@var{pred}, the second a list of those which do not.\n"
1704
"The elements in the result lists are in the same order as in\n"
1705
"@var{lst} but the order in which the calls @code{(@var{pred}\n"
1706
"elem)} are made on the list elements is unspecified.\n"
1708
"@var{lst} may be modified to construct the return lists.")
1709
#define FUNC_NAME s_scm_srfi1_partition_x
1711
SCM tlst, flst, *tp, *fp;
1712
scm_t_trampoline_1 pred_tramp;
1714
pred_tramp = scm_trampoline_1 (pred);
1715
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
1717
/* tlst and flst are the lists of true and false elements. tp and fp are
1718
where to store to append to them, initially &tlst and &flst, then
1719
SCM_CDRLOC of the last pair in the respective lists. */
1726
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
1728
if (scm_is_true (pred_tramp (pred, SCM_CAR (lst))))
1731
tp = SCM_CDRLOC (lst);
1736
fp = SCM_CDRLOC (lst);
1740
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
1742
/* terminate whichever didn't get the last element(s) */
1746
return scm_values (scm_list_2 (tlst, flst));
1751
SCM_DEFINE (scm_srfi1_reduce, "reduce", 3, 0, 0,
1752
(SCM proc, SCM def, SCM lst),
1753
"@code{reduce} is a variant of @code{fold}, where the first call\n"
1754
"to @var{proc} is on two elements from @var{lst}, rather than\n"
1755
"one element and a given initial value.\n"
1757
"If @var{lst} is empty, @code{reduce} returns @var{def} (this is\n"
1758
"the only use for @var{def}). If @var{lst} has just one element\n"
1759
"then that's the return value. Otherwise @var{proc} is called\n"
1760
"on the elements of @var{lst}.\n"
1762
"Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1763
"@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1764
"second and subsequent elements of @var{lst}), and\n"
1765
"@var{previous} is the return from the previous call to\n"
1766
"@var{proc}. The first element of @var{lst} is the\n"
1767
"@var{previous} for the first call to @var{proc}.\n"
1769
"For example, the following adds a list of numbers, the calls\n"
1770
"made to @code{+} are shown. (Of course @code{+} accepts\n"
1771
"multiple arguments and can add a list directly, with\n"
1775
"(reduce + 0 '(5 6 7)) @result{} 18\n"
1777
"(+ 6 5) @result{} 11\n"
1778
"(+ 7 11) @result{} 18\n"
1781
"@code{reduce} can be used instead of @code{fold} where the\n"
1782
"@var{init} value is an ``identity'', meaning a value which\n"
1783
"under @var{proc} doesn't change the result, in this case 0 is\n"
1784
"an identity since @code{(+ 5 0)} is just 5. @code{reduce}\n"
1785
"avoids that unnecessary call.")
1786
#define FUNC_NAME s_scm_srfi1_reduce
1788
scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc);
1791
SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME);
1793
ret = def; /* if lst is empty */
1794
if (scm_is_pair (lst))
1796
ret = SCM_CAR (lst); /* if lst has one element */
1798
for (lst = SCM_CDR (lst); scm_is_pair (lst); lst = SCM_CDR (lst))
1799
ret = proc_tramp (proc, SCM_CAR (lst), ret);
1802
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG3, FUNC_NAME, "list");
1808
SCM_DEFINE (scm_srfi1_reduce_right, "reduce-right", 3, 0, 0,
1809
(SCM proc, SCM def, SCM lst),
1810
"@code{reduce-right} is a variant of @code{fold-right}, where\n"
1811
"the first call to @var{proc} is on two elements from @var{lst},\n"
1812
"rather than one element and a given initial value.\n"
1814
"If @var{lst} is empty, @code{reduce-right} returns @var{def}\n"
1815
"(this is the only use for @var{def}). If @var{lst} has just\n"
1816
"one element then that's the return value. Otherwise @var{proc}\n"
1817
"is called on the elements of @var{lst}.\n"
1819
"Each @var{proc} call is @code{(@var{proc} @var{elem}\n"
1820
"@var{previous})}, where @var{elem} is from @var{lst} (the\n"
1821
"second last and then working back to the first element of\n"
1822
"@var{lst}), and @var{previous} is the return from the previous\n"
1823
"call to @var{proc}. The last element of @var{lst} is the\n"
1824
"@var{previous} for the first call to @var{proc}.\n"
1826
"For example, the following adds a list of numbers, the calls\n"
1827
"made to @code{+} are shown. (Of course @code{+} accepts\n"
1828
"multiple arguments and can add a list directly, with\n"
1832
"(reduce-right + 0 '(5 6 7)) @result{} 18\n"
1834
"(+ 6 7) @result{} 13\n"
1835
"(+ 5 13) @result{} 18\n"
1838
"@code{reduce-right} can be used instead of @code{fold-right}\n"
1839
"where the @var{init} value is an ``identity'', meaning a value\n"
1840
"which under @var{proc} doesn't change the result, in this case\n"
1841
"0 is an identity since @code{(+ 7 0)} is just 5.\n"
1842
"@code{reduce-right} avoids that unnecessary call.\n"
1844
"@code{reduce} should be preferred over @code{reduce-right} if\n"
1845
"the order of processing doesn't matter, or can be arranged\n"
1846
"either way, since @code{reduce} is a little more efficient.")
1847
#define FUNC_NAME s_scm_srfi1_reduce_right
1849
/* To work backwards across a list requires either repeatedly traversing
1850
to get each previous element, or using some memory for a reversed or
1851
random-access form. Repeated traversal might not be too terrible, but
1852
is of course quadratic complexity and hence to be avoided in case LST
1853
is long. A vector is preferred over a reversed list since it's more
1854
compact and is less work for the gc to collect. */
1856
scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc);
1860
SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME);
1862
if (SCM_NULL_OR_NIL_P (lst))
1865
vec = scm_vector (lst);
1866
len = SCM_SIMPLE_VECTOR_LENGTH (vec);
1868
ret = SCM_SIMPLE_VECTOR_REF (vec, len-1);
1869
for (i = len-2; i >= 0; i--)
1870
ret = proc_tramp (proc, SCM_SIMPLE_VECTOR_REF (vec, i), ret);
1877
SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0,
1878
(SCM pred, SCM list),
1879
"Return a list containing all elements from @var{lst} which do\n"
1880
"not satisfy the predicate @var{pred}. The elements in the\n"
1881
"result list have the same order as in @var{lst}. The order in\n"
1882
"which @var{pred} is applied to the list elements is not\n"
1884
#define FUNC_NAME s_scm_srfi1_remove
1886
scm_t_trampoline_1 call = scm_trampoline_1 (pred);
1890
SCM_ASSERT (call, pred, 1, FUNC_NAME);
1891
SCM_VALIDATE_LIST (2, list);
1893
for (prev = &res, walk = list;
1895
walk = SCM_CDR (walk))
1897
if (scm_is_false (call (pred, SCM_CAR (walk))))
1899
*prev = scm_cons (SCM_CAR (walk), SCM_EOL);
1900
prev = SCM_CDRLOC (*prev);
1909
SCM_DEFINE (scm_srfi1_remove_x, "remove!", 2, 0, 0,
1910
(SCM pred, SCM list),
1911
"Return a list containing all elements from @var{list} which do\n"
1912
"not satisfy the predicate @var{pred}. The elements in the\n"
1913
"result list have the same order as in @var{list}. The order in\n"
1914
"which @var{pred} is applied to the list elements is not\n"
1915
"specified. @var{list} may be modified to build the return\n"
1917
#define FUNC_NAME s_scm_srfi1_remove_x
1919
scm_t_trampoline_1 call = scm_trampoline_1 (pred);
1922
SCM_ASSERT (call, pred, 1, FUNC_NAME);
1923
SCM_VALIDATE_LIST (2, list);
1925
for (prev = &list, walk = list;
1927
walk = SCM_CDR (walk))
1929
if (scm_is_false (call (pred, SCM_CAR (walk))))
1930
prev = SCM_CDRLOC (walk);
1932
*prev = SCM_CDR (walk);
1940
SCM_DEFINE (scm_srfi1_seventh, "seventh", 1, 0, 0,
1942
"Return the seventh element of @var{lst}.")
1943
#define FUNC_NAME s_scm_srfi1_seventh
1945
return scm_list_ref (lst, scm_from_int (6));
1950
SCM_DEFINE (scm_srfi1_sixth, "sixth", 1, 0, 0,
1952
"Return the sixth element of @var{lst}.")
1953
#define FUNC_NAME s_scm_srfi1_sixth
1955
return scm_list_ref (lst, scm_from_int (5));
1960
SCM_DEFINE (scm_srfi1_span, "span", 2, 0, 0,
1961
(SCM pred, SCM lst),
1962
"Return two values, the longest initial prefix of @var{lst}\n"
1963
"whose elements all satisfy the predicate @var{pred}, and the\n"
1964
"remainder of @var{lst}.")
1965
#define FUNC_NAME s_scm_srfi1_span
1967
scm_t_trampoline_1 pred_tramp;
1970
pred_tramp = scm_trampoline_1 (pred);
1971
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
1975
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
1977
SCM elem = SCM_CAR (lst);
1978
if (scm_is_false (pred_tramp (pred, elem)))
1981
/* want this elem, tack it onto the end of ret */
1982
*p = scm_cons (elem, SCM_EOL);
1983
p = SCM_CDRLOC (*p);
1985
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
1988
return scm_values (scm_list_2 (ret, lst));
1993
SCM_DEFINE (scm_srfi1_span_x, "span!", 2, 0, 0,
1994
(SCM pred, SCM lst),
1995
"Return two values, the longest initial prefix of @var{lst}\n"
1996
"whose elements all satisfy the predicate @var{pred}, and the\n"
1997
"remainder of @var{lst}. @var{lst} may be modified to form the\n"
1999
#define FUNC_NAME s_scm_srfi1_span_x
2002
scm_t_trampoline_1 pred_tramp;
2004
pred_tramp = scm_trampoline_1 (pred);
2005
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
2008
for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto))
2010
if (scm_is_false (pred_tramp (pred, SCM_CAR (upto))))
2013
/* want this element */
2014
p = SCM_CDRLOC (upto);
2016
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list");
2020
return scm_values (scm_list_2 (lst, upto));
2025
SCM_DEFINE (scm_srfi1_split_at, "split-at", 2, 0, 0,
2027
"Return two values (multiple values), being a list of the\n"
2028
"elements before index @var{n} in @var{lst}, and a list of those\n"
2030
#define FUNC_NAME s_scm_srfi1_split_at
2033
/* pre is a list of elements before the i split point, loc is the CDRLOC
2034
of the last cell, ie. where to store to append to it */
2038
for (nn = scm_to_size_t (n); nn != 0; nn--)
2040
SCM_VALIDATE_CONS (SCM_ARG1, lst);
2042
*loc = scm_cons (SCM_CAR (lst), SCM_EOL);
2043
loc = SCM_CDRLOC (*loc);
2046
return scm_values (scm_list_2 (pre, lst));
2051
SCM_DEFINE (scm_srfi1_split_at_x, "split-at!", 2, 0, 0,
2053
"Return two values (multiple values), being a list of the\n"
2054
"elements before index @var{n} in @var{lst}, and a list of those\n"
2055
"after. @var{lst} is modified to form those values.")
2056
#define FUNC_NAME s_scm_srfi1_split_at
2062
for (nn = scm_to_size_t (n); nn != 0; nn--)
2064
SCM_VALIDATE_CONS (SCM_ARG1, upto);
2066
loc = SCM_CDRLOC (upto);
2067
upto = SCM_CDR (upto);
2071
return scm_values (scm_list_2 (lst, upto));
2076
SCM_DEFINE (scm_srfi1_take_x, "take!", 2, 0, 0,
2078
"Return a list containing the first @var{n} elements of\n"
2080
#define FUNC_NAME s_scm_srfi1_take_x
2085
nn = scm_to_signed_integer (n, 0, LONG_MAX);
2089
pos = scm_list_tail (lst, scm_from_long (nn - 1));
2091
/* Must have at least one cell left, mustn't have reached the end of an
2092
n-1 element list. SCM_VALIDATE_CONS here gives the same error as
2093
scm_list_tail does on say an n-2 element list, though perhaps a range
2094
error would make more sense (for both). */
2095
SCM_VALIDATE_CONS (SCM_ARG1, pos);
2097
SCM_SETCDR (pos, SCM_EOL);
2103
SCM_DEFINE (scm_srfi1_take_right, "take-right", 2, 0, 0,
2105
"Return the a list containing the @var{n} last elements of\n"
2107
#define FUNC_NAME s_scm_srfi1_take_right
2109
SCM tail = scm_list_tail (lst, n);
2110
while (scm_is_pair (tail))
2112
lst = SCM_CDR (lst);
2113
tail = SCM_CDR (tail);
2115
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list");
2121
SCM_DEFINE (scm_srfi1_take_while, "take-while", 2, 0, 0,
2122
(SCM pred, SCM lst),
2123
"Return a new list which is the longest initial prefix of\n"
2124
"@var{lst} whose elements all satisfy the predicate @var{pred}.")
2125
#define FUNC_NAME s_scm_srfi1_take_while
2127
scm_t_trampoline_1 pred_tramp;
2130
pred_tramp = scm_trampoline_1 (pred);
2131
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
2135
for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
2137
SCM elem = SCM_CAR (lst);
2138
if (scm_is_false (pred_tramp (pred, elem)))
2141
/* want this elem, tack it onto the end of ret */
2142
*p = scm_cons (elem, SCM_EOL);
2143
p = SCM_CDRLOC (*p);
2145
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
2153
SCM_DEFINE (scm_srfi1_take_while_x, "take-while!", 2, 0, 0,
2154
(SCM pred, SCM lst),
2155
"Return the longest initial prefix of @var{lst} whose elements\n"
2156
"all satisfy the predicate @var{pred}. @var{lst} may be\n"
2157
"modified to form the return.")
2158
#define FUNC_NAME s_scm_srfi1_take_while_x
2161
scm_t_trampoline_1 pred_tramp;
2163
pred_tramp = scm_trampoline_1 (pred);
2164
SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME);
2167
for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto))
2169
if (scm_is_false (pred_tramp (pred, SCM_CAR (upto))))
2172
/* want this element */
2173
p = SCM_CDRLOC (upto);
2175
SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list");
2184
SCM_DEFINE (scm_srfi1_tenth, "tenth", 1, 0, 0,
2186
"Return the tenth element of @var{lst}.")
2187
#define FUNC_NAME s_scm_srfi1_tenth
2189
return scm_list_ref (lst, scm_from_int (9));
2194
SCM_DEFINE (scm_srfi1_xcons, "xcons", 2, 0, 0,
2196
"Like @code{cons}, but with interchanged arguments. Useful\n"
2197
"mostly when passed to higher-order procedures.")
2198
#define FUNC_NAME s_scm_srfi1_xcons
2200
return scm_cons (a, d);
2206
scm_init_srfi_1 (void)
2208
SCM the_root_module = scm_lookup_closure_module (SCM_BOOL_F);
2209
#ifndef SCM_MAGIC_SNARFER
2210
#include "srfi/srfi-1.x"
2212
scm_c_extend_primitive_generic
2213
(SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "map")),
2214
SCM_VARIABLE_REF (scm_c_lookup ("map")));
2215
scm_c_extend_primitive_generic
2216
(SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "for-each")),
2217
SCM_VARIABLE_REF (scm_c_lookup ("for-each")));
2220
/* End of srfi-1.c. */
added
removed
srfi/srfi-1.c
